#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define F first
#define S second
#define PB push_back
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int MXN = 1e6+5;
int n, a, b;
int T[MXN];
int dp[MXN];
multiset<int> MS1;
multiset<int> MS2;
vector<int> event[2*MXN];
bool moved[2*MXN];
int main() {
FASTIO();
cin >> n >> a >> b;
for(int i = 1; i <= n; i++) {
cin >> T[i];
}
sort(T+1, T+n+1);
fill(dp, dp+n+1, MXN);
dp[0] = 0;
int j = 0;
for(int i = 1; i <= n; i++) {
for(; j <= T[i]; j++) {
//cerr << "j = " << j << "\n";
while(!event[j].empty()) {
int x = event[j].back();
if(moved[x]) {
event[j].pop_back();
continue;
}
moved[x] = true;
MS1.erase(MS1.find(dp[x]));
MS2.insert(T[x+1]);
event[j].pop_back();
}
} j--;
int l = i-b, r = i-a;
if(r < 0) continue;
if(l-1 >= 0) {
if(!moved[l-1]) MS1.erase(MS1.find(dp[l-1]));
else MS2.erase(MS2.find(T[l]));
moved[l-1] = true;
}
if(T[r+1]+dp[r] > T[i]) {
MS1.insert(dp[r]);
event[T[r+1]+dp[r]].PB(r);
}
else {
moved[r] = true;
MS2.insert(T[r+1]);
}
if(!MS1.empty()) dp[i] = min(dp[i], *MS1.begin());
if(!MS2.empty()) dp[i] = min(dp[i], T[i]-(*MS2.rbegin()));
}
cout << dp[n] << "\n";
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47180 KB |
Output is correct |
2 |
Correct |
37 ms |
48720 KB |
Output is correct |
3 |
Correct |
29 ms |
47624 KB |
Output is correct |
4 |
Correct |
282 ms |
80756 KB |
Output is correct |
5 |
Correct |
288 ms |
75856 KB |
Output is correct |
6 |
Correct |
48 ms |
50268 KB |
Output is correct |
7 |
Correct |
251 ms |
73968 KB |
Output is correct |
8 |
Correct |
24 ms |
47312 KB |
Output is correct |
9 |
Correct |
26 ms |
47208 KB |
Output is correct |
10 |
Correct |
25 ms |
47188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47312 KB |
Output is correct |
2 |
Correct |
26 ms |
47208 KB |
Output is correct |
3 |
Correct |
25 ms |
47188 KB |
Output is correct |
4 |
Correct |
27 ms |
47188 KB |
Output is correct |
5 |
Correct |
24 ms |
47288 KB |
Output is correct |
6 |
Correct |
24 ms |
47228 KB |
Output is correct |
7 |
Correct |
24 ms |
47432 KB |
Output is correct |
8 |
Correct |
23 ms |
47220 KB |
Output is correct |
9 |
Correct |
25 ms |
47192 KB |
Output is correct |
10 |
Correct |
22 ms |
47188 KB |
Output is correct |
11 |
Correct |
26 ms |
47308 KB |
Output is correct |
12 |
Correct |
27 ms |
47188 KB |
Output is correct |
13 |
Correct |
22 ms |
47192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47180 KB |
Output is correct |
2 |
Correct |
37 ms |
48720 KB |
Output is correct |
3 |
Correct |
29 ms |
47624 KB |
Output is correct |
4 |
Correct |
282 ms |
80756 KB |
Output is correct |
5 |
Correct |
288 ms |
75856 KB |
Output is correct |
6 |
Correct |
48 ms |
50268 KB |
Output is correct |
7 |
Correct |
251 ms |
73968 KB |
Output is correct |
8 |
Correct |
24 ms |
47312 KB |
Output is correct |
9 |
Correct |
26 ms |
47208 KB |
Output is correct |
10 |
Correct |
25 ms |
47188 KB |
Output is correct |
11 |
Correct |
27 ms |
47188 KB |
Output is correct |
12 |
Correct |
24 ms |
47288 KB |
Output is correct |
13 |
Correct |
24 ms |
47228 KB |
Output is correct |
14 |
Correct |
24 ms |
47432 KB |
Output is correct |
15 |
Correct |
23 ms |
47220 KB |
Output is correct |
16 |
Correct |
25 ms |
47192 KB |
Output is correct |
17 |
Correct |
22 ms |
47188 KB |
Output is correct |
18 |
Correct |
26 ms |
47308 KB |
Output is correct |
19 |
Correct |
27 ms |
47188 KB |
Output is correct |
20 |
Correct |
22 ms |
47192 KB |
Output is correct |
21 |
Correct |
32 ms |
48212 KB |
Output is correct |
22 |
Correct |
28 ms |
47724 KB |
Output is correct |
23 |
Correct |
37 ms |
48036 KB |
Output is correct |
24 |
Correct |
48 ms |
50300 KB |
Output is correct |
25 |
Correct |
111 ms |
53332 KB |
Output is correct |
26 |
Correct |
284 ms |
71500 KB |
Output is correct |
27 |
Correct |
59 ms |
50264 KB |
Output is correct |
28 |
Correct |
38 ms |
48092 KB |
Output is correct |
29 |
Correct |
22 ms |
47284 KB |
Output is correct |
30 |
Correct |
443 ms |
75444 KB |
Output is correct |
31 |
Correct |
459 ms |
76040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47180 KB |
Output is correct |
2 |
Correct |
37 ms |
48720 KB |
Output is correct |
3 |
Correct |
29 ms |
47624 KB |
Output is correct |
4 |
Correct |
282 ms |
80756 KB |
Output is correct |
5 |
Correct |
288 ms |
75856 KB |
Output is correct |
6 |
Correct |
48 ms |
50268 KB |
Output is correct |
7 |
Correct |
251 ms |
73968 KB |
Output is correct |
8 |
Correct |
24 ms |
47312 KB |
Output is correct |
9 |
Correct |
26 ms |
47208 KB |
Output is correct |
10 |
Correct |
25 ms |
47188 KB |
Output is correct |
11 |
Correct |
32 ms |
48212 KB |
Output is correct |
12 |
Correct |
28 ms |
47724 KB |
Output is correct |
13 |
Correct |
37 ms |
48036 KB |
Output is correct |
14 |
Correct |
48 ms |
50300 KB |
Output is correct |
15 |
Correct |
111 ms |
53332 KB |
Output is correct |
16 |
Correct |
284 ms |
71500 KB |
Output is correct |
17 |
Correct |
59 ms |
50264 KB |
Output is correct |
18 |
Correct |
38 ms |
48092 KB |
Output is correct |
19 |
Correct |
22 ms |
47284 KB |
Output is correct |
20 |
Correct |
443 ms |
75444 KB |
Output is correct |
21 |
Correct |
459 ms |
76040 KB |
Output is correct |
22 |
Correct |
27 ms |
47188 KB |
Output is correct |
23 |
Correct |
24 ms |
47288 KB |
Output is correct |
24 |
Correct |
24 ms |
47228 KB |
Output is correct |
25 |
Correct |
24 ms |
47432 KB |
Output is correct |
26 |
Correct |
23 ms |
47220 KB |
Output is correct |
27 |
Correct |
25 ms |
47192 KB |
Output is correct |
28 |
Correct |
22 ms |
47188 KB |
Output is correct |
29 |
Correct |
26 ms |
47308 KB |
Output is correct |
30 |
Correct |
27 ms |
47188 KB |
Output is correct |
31 |
Correct |
22 ms |
47192 KB |
Output is correct |
32 |
Correct |
37 ms |
48220 KB |
Output is correct |
33 |
Correct |
236 ms |
56596 KB |
Output is correct |
34 |
Correct |
169 ms |
54056 KB |
Output is correct |
35 |
Correct |
534 ms |
99280 KB |
Output is correct |
36 |
Correct |
570 ms |
92864 KB |
Output is correct |
37 |
Correct |
412 ms |
79948 KB |
Output is correct |
38 |
Correct |
256 ms |
55472 KB |
Output is correct |