#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
using pll = pair<ld, int>;
using pii = pair<int, int>;
#define f first
#define s second
const int inf = 1e9;
struct ST{
vector<ld> t, p;
vector<int> k;
int n;
void build(int v, int tl, int tr){
if (tl == tr){
k[v] = tl;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
build(vv, tl, tm);
build(vv + 1, tm + 1, tr);
t[v] = tl;
}
ST(int ns){
n = ns;
t.resize(4 * n);
p.resize(4 * n);
k.resize(4 * n);
build(1, 1, n);
}
void push(int& v, int& vv){
if (!p[v]) return;
p[vv] += p[v]; t[vv] += p[v];
p[vv + 1] += p[v]; t[vv + 1] += p[v];
p[v] = 0;
}
void add(int v, int tl, int tr, int& l, int& r, ld& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
t[v] += x;
p[v] += x;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
if (t[vv] > t[vv + 1]){
t[v] = t[vv + 1];
k[v] = k[vv + 1];
}
else {
t[v] = t[vv];
k[v] = k[vv];
}
t[v] = min(t[vv], t[vv + 1]);
}
void add(int l, int r, ld x){
if (l > r) return;
add(1, 1, n, l, r, x);
}
pll get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return {inf, 0};
if (l <= tl && tr <= r){
return {t[v], k[v]};
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
pll get(int l, int r){
return get(1, 1, n, l, r);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, d, t; cin>>n>>d>>t;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin>>a[i];
}
vector<int> h(n + 1);
int mx = 0, cnt = 0;
for (int j = 1; j <= n; j++){
if (a[j] <= t){
int m = t - a[j];
mx = max(mx, j + m);
}
cnt += (j <= mx);
h[j] = cnt;
}
vector<int> r(n + 1);
for (int i = 1; i <= n; i++){
if (a[i] > t) continue;
int m = t - a[i];
r[i] = i + m;
}
const int lg = ceil(log2(n));
vector<vector<int>> sp(n + 1, vector<int>(lg));
for (int i = 1; i <= n; i++){
sp[i][0] = r[i];
}
for (int j = 1; j < lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
vector<int> log(n + 1);
for (int i = 2; i <= n; i++){
log[i] = log[i / 2] + 1;
}
auto check = [&](int x, int y){
int k = log[y - x + 1];
return max(sp[x][k], sp[y - (1 << k) + 1][k]) >= y;
};
vector<int> f(n);
for (int i = 1; i < n; i++){
auto good = [&](int m){
return check(m, i + 1);
};
int l = 0, r = i + 1;
while (l + 1 < r){
int m = (l + r) / 2;
if (good(m)){
l = m;
}
else {
r = m - 1;
}
}
if (good(r)) l = r;
f[i] = l;
}
auto solve = [&](ld m){
pll dp[n + 1];
ST T(n);
for (int i = 1; i <= n; i++){
dp[i] = {h[i], 0};
T.add(1, f[i - 1] - 1, 1);
auto [v, j] = T.get(1, i - 1);
dp[i] = min(dp[i], {v + m, dp[j].s + 1});
T.add(i, i, dp[i].f);
}
return dp[n];
};
ld lb = 0, rb = n;
int tt = 40;
while (tt--){
ld m = (lb + rb) / 2;
auto [v, k] = solve(m);
if (k > d){
lb = m;
}
else {
rb = m;
}
}
auto [v, k] = solve(lb);
cout<<round(v - lb * d)<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
544 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
540 KB |
Output is correct |
11 |
Correct |
6 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
2085 ms |
116088 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
544 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
540 KB |
Output is correct |
11 |
Correct |
6 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
14 |
Correct |
5 ms |
348 KB |
Output is correct |
15 |
Correct |
6 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
348 KB |
Output is correct |
18 |
Correct |
7 ms |
344 KB |
Output is correct |
19 |
Correct |
6 ms |
600 KB |
Output is correct |
20 |
Correct |
6 ms |
548 KB |
Output is correct |
21 |
Correct |
6 ms |
348 KB |
Output is correct |
22 |
Correct |
6 ms |
544 KB |
Output is correct |
23 |
Correct |
66 ms |
1248 KB |
Output is correct |
24 |
Correct |
66 ms |
1252 KB |
Output is correct |
25 |
Correct |
68 ms |
1252 KB |
Output is correct |
26 |
Correct |
65 ms |
1228 KB |
Output is correct |
27 |
Correct |
68 ms |
1256 KB |
Output is correct |
28 |
Correct |
66 ms |
1216 KB |
Output is correct |
29 |
Correct |
66 ms |
1252 KB |
Output is correct |
30 |
Correct |
63 ms |
1524 KB |
Output is correct |
31 |
Correct |
59 ms |
1216 KB |
Output is correct |
32 |
Correct |
62 ms |
1248 KB |
Output is correct |
33 |
Correct |
64 ms |
1244 KB |
Output is correct |
34 |
Correct |
67 ms |
1244 KB |
Output is correct |
35 |
Correct |
68 ms |
1224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1571 ms |
16808 KB |
Output is correct |
3 |
Correct |
1567 ms |
16604 KB |
Output is correct |
4 |
Correct |
1519 ms |
16792 KB |
Output is correct |
5 |
Correct |
1482 ms |
16772 KB |
Output is correct |
6 |
Correct |
1491 ms |
17008 KB |
Output is correct |
7 |
Correct |
1337 ms |
16848 KB |
Output is correct |
8 |
Correct |
1308 ms |
16636 KB |
Output is correct |
9 |
Correct |
1475 ms |
16856 KB |
Output is correct |
10 |
Correct |
1450 ms |
16764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
544 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
540 KB |
Output is correct |
11 |
Correct |
6 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
14 |
Correct |
5 ms |
348 KB |
Output is correct |
15 |
Correct |
6 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
348 KB |
Output is correct |
18 |
Correct |
7 ms |
344 KB |
Output is correct |
19 |
Correct |
6 ms |
600 KB |
Output is correct |
20 |
Correct |
6 ms |
548 KB |
Output is correct |
21 |
Correct |
6 ms |
348 KB |
Output is correct |
22 |
Correct |
6 ms |
544 KB |
Output is correct |
23 |
Correct |
66 ms |
1248 KB |
Output is correct |
24 |
Correct |
66 ms |
1252 KB |
Output is correct |
25 |
Correct |
68 ms |
1252 KB |
Output is correct |
26 |
Correct |
65 ms |
1228 KB |
Output is correct |
27 |
Correct |
68 ms |
1256 KB |
Output is correct |
28 |
Correct |
66 ms |
1216 KB |
Output is correct |
29 |
Correct |
66 ms |
1252 KB |
Output is correct |
30 |
Correct |
63 ms |
1524 KB |
Output is correct |
31 |
Correct |
59 ms |
1216 KB |
Output is correct |
32 |
Correct |
62 ms |
1248 KB |
Output is correct |
33 |
Correct |
64 ms |
1244 KB |
Output is correct |
34 |
Correct |
67 ms |
1244 KB |
Output is correct |
35 |
Correct |
68 ms |
1224 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1571 ms |
16808 KB |
Output is correct |
38 |
Correct |
1567 ms |
16604 KB |
Output is correct |
39 |
Correct |
1519 ms |
16792 KB |
Output is correct |
40 |
Correct |
1482 ms |
16772 KB |
Output is correct |
41 |
Correct |
1491 ms |
17008 KB |
Output is correct |
42 |
Correct |
1337 ms |
16848 KB |
Output is correct |
43 |
Correct |
1308 ms |
16636 KB |
Output is correct |
44 |
Correct |
1475 ms |
16856 KB |
Output is correct |
45 |
Correct |
1450 ms |
16764 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
5 ms |
348 KB |
Output is correct |
48 |
Correct |
5 ms |
348 KB |
Output is correct |
49 |
Correct |
8 ms |
348 KB |
Output is correct |
50 |
Correct |
6 ms |
544 KB |
Output is correct |
51 |
Correct |
6 ms |
344 KB |
Output is correct |
52 |
Correct |
6 ms |
348 KB |
Output is correct |
53 |
Correct |
7 ms |
548 KB |
Output is correct |
54 |
Correct |
7 ms |
344 KB |
Output is correct |
55 |
Correct |
6 ms |
348 KB |
Output is correct |
56 |
Correct |
6 ms |
348 KB |
Output is correct |
57 |
Correct |
68 ms |
1248 KB |
Output is correct |
58 |
Correct |
67 ms |
1248 KB |
Output is correct |
59 |
Correct |
67 ms |
1248 KB |
Output is correct |
60 |
Correct |
66 ms |
1248 KB |
Output is correct |
61 |
Correct |
72 ms |
1280 KB |
Output is correct |
62 |
Correct |
67 ms |
1248 KB |
Output is correct |
63 |
Correct |
66 ms |
1248 KB |
Output is correct |
64 |
Correct |
60 ms |
1252 KB |
Output is correct |
65 |
Correct |
60 ms |
1228 KB |
Output is correct |
66 |
Correct |
65 ms |
1224 KB |
Output is correct |
67 |
Correct |
62 ms |
1256 KB |
Output is correct |
68 |
Correct |
67 ms |
1248 KB |
Output is correct |
69 |
Correct |
65 ms |
1248 KB |
Output is correct |
70 |
Correct |
0 ms |
344 KB |
Output is correct |
71 |
Correct |
1590 ms |
16852 KB |
Output is correct |
72 |
Correct |
1610 ms |
16808 KB |
Output is correct |
73 |
Correct |
1501 ms |
16756 KB |
Output is correct |
74 |
Correct |
1501 ms |
16760 KB |
Output is correct |
75 |
Correct |
1486 ms |
16612 KB |
Output is correct |
76 |
Correct |
1358 ms |
16612 KB |
Output is correct |
77 |
Correct |
1324 ms |
16612 KB |
Output is correct |
78 |
Correct |
1447 ms |
16612 KB |
Output is correct |
79 |
Correct |
1500 ms |
17016 KB |
Output is correct |
80 |
Correct |
1603 ms |
17372 KB |
Output is correct |
81 |
Correct |
1527 ms |
17440 KB |
Output is correct |
82 |
Correct |
1553 ms |
17460 KB |
Output is correct |
83 |
Correct |
1550 ms |
17408 KB |
Output is correct |
84 |
Correct |
1551 ms |
17012 KB |
Output is correct |
85 |
Correct |
1502 ms |
18124 KB |
Output is correct |
86 |
Correct |
1433 ms |
17148 KB |
Output is correct |
87 |
Correct |
1348 ms |
17332 KB |
Output is correct |
88 |
Correct |
1406 ms |
17212 KB |
Output is correct |
89 |
Correct |
1040 ms |
17504 KB |
Output is correct |
90 |
Correct |
1157 ms |
17408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
348 KB |
Output is correct |
7 |
Correct |
8 ms |
544 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
348 KB |
Output is correct |
10 |
Correct |
6 ms |
540 KB |
Output is correct |
11 |
Correct |
6 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Execution timed out |
2085 ms |
116088 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |