11108번 - TV 전쟁 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 152 | 51 | 47 | 38.843% |
문제
나는 티비가 하나밖에 없는 집에 가족과 함께 살고 있다. 그래서 어떤 tv프로그램을 볼 지 늘 가족과 다투는 경우가 많다. 따라서 이를 자동으로 해결해 줄 기계를 만들고자 한다.
한 해동안 내 가족들이 보고자 하는 tv프로그램은 정해져있다. 그것들은 매주 늘 같은 시각에 시작해서 정확히 같은 시각에 끝난다. 따라서 한 주에 대해서 어떤 프로그램을 볼 지 정해놓고 그 방식대로 1년간 진행하면 되는 것이다. 각 프로그램들은 가족들로부터 일정한 점수를 받는데 이 점수가 높을 수록 가족이 선호하는 프로그램이라는 뜻이된다. 이러한 프로그램들을 볼때 점수의 총합이 가장 큰 방향으로 tv스케줄을 정하기로 가족이 합의했다. 하지만 나는 능력이 부족하여 가상의 여자친구에게 이 스케줄을 자동으로 만들어주는 기계를 만들어달라고 부탁했다. 하지만 가상의 여자친구도 이것이 귀찮아 여러분들에게 부탁을 하고자 한다.
입력
첫 번째 줄에 주어지는 t는 테스트 케이스의 개수이다. 각 테스트 케이스의 첫 줄은 tv프로그램의 개수 n(1 ≤ n ≤ 100000)이 주어진다. 그리고 n줄에 걸쳐서 공백으로 구분된 3개의 정수 s, d, p가 주어진다. s는 프로그램의 시작시간, d는 프로그램의 지속시간을 나타내고 p는 그 프로그램에 대한 가족들의 선호도이다. (0 ≤ s < s+d ≤ 10080, 1 ≤ p ≤ 2000) 만약 s+d=k라고 할때 이 프로그램은 정확히 k시각에 끝나는 것이고 새 프로그램을 정확히 k시각부터 볼 수 있다.
출력
각 테스트 케이스 별로 한줄에 선호도의 총합의 최댓값을 출력한다.
예제 입력 1
1 3 3 8 10 1 4 6 6 4 5
예제 출력 1
11
힌트
1부터 4동안 지속되는 프로그램과 6부터 4동안 진행되는 프로그램을 보면 선호도의 총합은 6+5=11이 되고 이것이 가족이 얻을 수 있는 선호도의 합의 최대가 된다.
출처
Contest > IDI Open Contest > IDI Open 2008 B번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호