레이팅 미적용소 베시에게는 당신이 완료할 수도 있는 \(N\)(\(1\le N\le 2\cdot 10^5\))개의 작업이 있다. \(i\)번째 작업은, 완료하기로 선택한다면 시각 \(s_i\) 이전 또는 정확히 그 시각에 시작해야 하며, 완료하는 데 \(t_i\)의 시간이 걸린다 (\(0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}\)).
완료할 수 있는 작업의 최대 개수는 몇 개일까? 시간은 \(0\)에서 시작하며, 한 작업을 시작하면 완료될 때까지 계속 그 작업만 해야 하고 그동안 다른 작업을 시작할 수 없다.
문제 제공: Benjamin Qi
배점
- 입력 2: 같은 테스트 케이스 안에서 모든 \(t_i\)가 같다.
- 입력 3-4: \(N\le 2000\), \(s_i, t_i\le 2000\)
- 입력 5-8: \(N\le 2000\)
- 입력 9-16: 추가 제약 없음.
문제 제공: Benjamin Qi
첫째 줄에 독립적인 테스트 케이스의 수 \(T\)(\(1\le T\le 10\))가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 두 정수 \(s_i\)와 \(t_i\)가 각각 주어진다. \(i+1\)번째 줄에 \(i\)번째 작업의 정보가 있다.
모든 테스트 케이스에 대한 \(N\)의 합이 \(3\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트 케이스에 대해, 완료할 수 있는 작업의 최대 개수를 한 줄에 출력한다.
3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 21
2
2For the first test case, you can only complete one of the jobs. After completing
one job, it will then be time \(2\) or later, so it is too late to start the other
job, which must be started at time \(1\) or earlier.
For the second test case, you can start the second job at time \(0\) and finish
at time \(2\), then start the first job at time \(2\) and finish at time \(5\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Gold