문제 설명
안녕하세요. KoreaTech 학우님들!
저는 KoreaTech 경제 연구소에서 재직 중인 소장 J라고 합니다.
다름이 아니라, 이번 국가 프로젝트의 일환으로 저희 연구소에서 새로운 시장 경제 모델을 개발하였는데요.
이에 대한 초기 모델 테스트를 위해 KoreaTech 학우분들을 초대합니다.!
저희가 이번에 개발한 시장 경제 모델의 규칙은 다음과 같습니다.
예시 1>
예시 2>
저는 KoreaTech 경제 연구소에서 재직 중인 소장 J라고 합니다.
다름이 아니라, 이번 국가 프로젝트의 일환으로 저희 연구소에서 새로운 시장 경제 모델을 개발하였는데요.
이에 대한 초기 모델 테스트를 위해 KoreaTech 학우분들을 초대합니다.!
저희가 이번에 개발한 시장 경제 모델의 규칙은 다음과 같습니다.
- 2차원으로 구성된 좌표계가 주어집니다.
- 이때 Y 축은 현재 최저 임금을, X는 시간을 의미합니다.
- 그리고 여러분께는 [시작 시기, 신규 추가 임금 정책 금액]으로 구성된 pair 값을 제공해 드릴 예정입니다.
- 시작 시기 : 최초 신규 추가 입금을 적용하는 시기를 의미합니다. (시작 시기의 입력은 시간 순서대로가 아닌 무작위 순서로 주어집니다.)
- 신규 추가 임금 정책 : 주어진 시작 시기를 기점으로 신규 추가 임금 정책의 금액만큼 해당 시작 시점을 기준으로 임금이 추가됩니다. 또한 신규로 상정된 임금은 (시작 시기 + 신규 추가 임금 정책 금액) 만큼의 기간 동안 영향력을 발휘합니다.
- 단, 이전에 추가된 신규 추가 임금 정책의 범위 외에 신규로 적용하는 모든 신규 추가 임금들은 0의 금액부터 시작됩니다.
- 이때, 주어진 pair의 개수 만큼, 해당 구간에서 가장 높게 누적된 임금을 리포팅해 주세요. (누적에 관한 조건은 위의 pair 구성 규칙을 참고해 주세요.)
- 단, 이전의 누적된 변동 내역보다 지금의 누적된 변경 내역이 작을 경우 이전의 높은 변경 내역을 적용합니다.
예시 1>
- 입력
- [[2,2],[3,1],[4,1]]
- 출력
- [2,3,3]
예시 2>
- 입력
- [[9,7],[1,9],[3,1]]
- 출력
- [7,16,17]
입력 설명
첫 줄에는 테스트케이스 T(1 ≤ T ≤ 10)가 주어집니다.
각 테스트케이스는 두 줄로 주어집니다.
첫 줄에는 총 pair의 개수 B(1 ≤ B ≤ 3000)가 주어집니다.
둘째 줄에는 B개의 pair S(1 ≤ S ≤ 109)와 P(1 ≤ P ≤ 105)가 주어집니다. 여기서 S는 시작 시기를 의미하고, P는 신규 추가 입금 정책을 의미합니다.
각 테스트케이스는 두 줄로 주어집니다.
첫 줄에는 총 pair의 개수 B(1 ≤ B ≤ 3000)가 주어집니다.
둘째 줄에는 B개의 pair S(1 ≤ S ≤ 109)와 P(1 ≤ P ≤ 105)가 주어집니다. 여기서 S는 시작 시기를 의미하고, P는 신규 추가 입금 정책을 의미합니다.
출력 설명
pair의 개수 만큼, 해당 구간에서 가장 높게 누적된 임금을 출력해주세요.
입력 예시 Copy
3
3
2 2 3 1 4 1
3
9 7 1 9 3 1
3
4 6 4 2 4 3
출력 예시 Copy
2 3 3
7 16 17
6 8 11