Autobahn
레이팅 미적용의견: 0
Croatian Olympiad in Informatics
April \(25^{th}\) 2021
There are \(N\) people testing their racing cars on notorious autobahn where limits do not exist. In this task
however limits do exist. So we kindly ask you to restrain yourself from submitting exponential complexity
solutions.
Person \(i\) came to autobahn at the beginning of minute \(l_{i}\), paid for \(t_{i}\) minutes of stay and left at the end of
minute \(r\)\(i\). Unfortunately some stayed for longer than that they have paid for. Administration of autobahn
decided not to be very harsh and charge them only for those extra minutes in which there were at least \(K\)
people on autobahn.
In a rush of generosity, administration decided to introduce happy hour i.e. interval of continuous \(X\)
minutes for which they won’t be paying extra charges. They picked happy hour so that the sum of extra
charges that won’t be paid is maximal possible. Determine that sum.
Subtask 1 (20 points): \(1 \le N\), K, X, l\(i\), t\(i\), r\(i \le 100\)
Subtask 2 (30 points): \(1 \le N\), K, X, l_{i}, t_{i}, \(r_{i} \le 1\,000\)
Subtask 3 (50 points): \(1 \le N \le 10^{5}\), \(1 \le X\), l\(i\), t\(i\), r\(i \le 10^{9}\)
First line contains integers \(N\), \(K\) and \(X\) (\(K \le N\)) from task description.
Next \(N\) lines contain integers \(l@@RISE_MATH_BLOCK_0@@i\) and \(r@@RISE_MATH_BLOCK_1@@i \le r\)\(i\)) from task description.
Print the required sum in a single line.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(1 \le N\), K, X, l\(i\), t\(i\), r\(i \le 100\) |
2 | 30점 | \(1 \le N\), K, X, l_{i}, t_{i}, \(r_{i} \le 1\,000\) |
3 | 50점 | \(1 \le N \le 10^{5}\), \(1 \le X\), l\(i\), t\(i\), r\(i \le 10^{9}\) |
5 3 4
2 1 4
3 3 7
3 3 8
1 5 7
5 3 873 2 22
7 16 33
69 14 88
8 10 9727
First sample explanation: Happy hour will span from 4th until the 7th minute. Inside that interval,
first person should’ve paid extra for the 4th minute and second, third and fourth person should’ve paid
for 6th and 7th minute.
1 od 7평가 및 의견
Autobahn
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Autobahn