USACO 2006 December Silver, poj 3257- 롤러코스터 > 문제은행 : 정보올림피아드&알고리즘




1546 : 롤러코스터

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
12 회   
시도횟수
30 회   

문제

소들이 롤러코스터를 만들고자 한다! 그들을 도와 가장 재미있는 롤러코스터를 설계해 보자.

 

 

롤러코스터의 가로 길이는 L(1≤L≤1,000)로 주어진다.

소들은 다양한 롤러 코스터 구성 요소를 함께 연결하는데

각 구성 요소의 끝 (마지막 구성 요소 제외)이 다음 구성 요소의 시작이 되도록 하여

0에서 시작하고 L에서 끝나는 롤러코드터를 만들고자 한다.

 

우리가 사용할 수 있는 구간은 총 N(1≤N≤10,000)개로 주어진다.

각 부품이 놓일 수 있는 가로 위치는 Xi로 정해져 있다.

또한 구간의 가로길이도 Wi로 주어져 있다.

또한 그 구간을 사용할 경우 드는 비용 Ci(1≤Ci≤1,000)와 재미있는 정도 Fi(1≤Fi≤1,000,000)도 주어져 있다.

 

소들은 롤러코스터를 만들기 위해 B(1≤B≤1,000)만큼의 예산을 마련해 놓았다.

구간들의 비용의 합이 예산을 넘지 않으면서 가장 재미도의 합이 가장 큰 롤러코스터를 설계해야한다.

물론 롤러코스터가 끊겨서는 안 된다.​ 


입력형식

L, N, B가 입력된다. 다음 N줄에 걸쳐 각 구간의 Xi, Wi, Fi, Ci가 주어진다.

출력형식

최대 재미도의 합을 출력한다. 만약 조건에 맞추어 설계가 불가능하다면 -1을 출력한다.

입력 예

5 6 10 
0 2 20 6 
2 3 5 6 
0 1 2 1 
1 1 1 3 
1 2 5 4 
3 2 10 2

출력 예

17


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP