#8187
서브태스크

Job Completion 1초 1024MB

문제

Bessie the cow has N (1≤N≤2⋅10^5) jobs for you to potentially complete. The i-th one, if you choose to complete it, must be started at or before time s_i and takes t_i time to complete (0≤s_i≤10^{18},1≤t_i≤10^{18}).What is the maximum number of jobs you can complete? Time starts at 0, and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.

입력

The first line contains

T

, the number of independent test cases (

1≤T≤10

). Each test case is formatted as follows.

The first line contains $N$ .

Each of the next $N$ lines contains two integers $s_i$ and $t_i$ . Row $i+1$ has the details for the $i$ th job.

It is guaranteed that the sum of $N$ over all test cases does not exceed $3⋅10^5$ .

출력

For each test case, the maximum number of jobs you can complete, on a new line.

부분문제

번호	점수	조건
#1	10점	Within the same test case, all $t_i$ are equal.
#2	20점	$N≤2000 , s_i,t_i≤2000$
#3	30점	$N≤2000$
#4	40점	No additional constraints.

예제1

3keyboard_return
2keyboard_return
1space_bar 4keyboard_return
1space_bar 2keyboard_return
2keyboard_return
2space_bar 3keyboard_return
1space_bar 2keyboard_return
3keyboard_return
1space_bar 4keyboard_return
2space_bar 3keyboard_return
1space_bar 2

1keyboard_return
2keyboard_return
2

For 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$ .

출처

USACO 2024 December Gold

역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.

#8187 upload 6회 done -회 how_to_reg -명 call_split 서브태스크

Job Completion timer 1초 memory 1024MB

문제 picture_in_picture_alt text_fields

입력

출력

부분문제

예제1

출처

역링크 공식 문제집만

#8187
서브태스크

Job Completion 1초 1024MB

문제