#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 4000 + 2;
const int inf = 1e9;
int st[4 * N], lzy[4 * N];
void Propagate(int node, int l, int r) {
if (lzy[node] == 0) return;
if (l < r) {
lzy[2 * node] += lzy[node];
lzy[2 * node + 1] += lzy[node];
}
st[node] += lzy[node];
lzy[node] = 0;
}
void Add(int node, int l, int r, int ql, int qr, int x) {
Propagate(node, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lzy[node] += x;
Propagate(node, l, r);
return;
}
int mid = l + r >> 1;
Add(2 * node, l, mid, ql, qr, x);
Add(2 * node + 1, mid + 1, r, ql, qr, x);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
int Get(int node, int l, int r, int ql, int qr) {
Propagate(node, l, r);
if (r < ql || qr < l) return 0;
if (ql <= l && r <= qr) return st[node];
int mid = l + r >> 1;
return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
void Dodaj(int l, int r, int o) {
Add(1, 0, N, l, r, o);
}
int cost[N][N], rmx[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, d, t;
cin >> n >> d >> t;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
stack<int> s;
vector<int> gr(n, inf);
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] > t) {
while (!s.empty() && a[s.top()] - s.top() + i > t) s.pop();
if (!s.empty()) {
gr[i] = s.top();
ans += 1;
}
}
s.push(i);
}
for (int i = 0; i < n; i++) if (a[i] <= t) ans++;
vector<array<int, 2>> svi;
for (int i = 0; i < n; i++) {
if (gr[i] != inf) svi.push_back({gr[i] + 1, i});
}
if (d == 1) {
vector<int> su(n);
for (int i = 0; i < svi.size(); i++) {
su[svi[i][0]] += 1;
su[svi[i][1] + 1] -= 1;
}
int mx = 0;
for (int i = 0; i < n; i++) {
if (i > 0) su[i] += su[i - 1];
smax(mx, su[i]);
}
cout << ans - mx << en;
return 0;
}
sort(svi.begin(), svi.end());
n = svi.size();
for (int i = 0; i < n; i++) {
int y = 0;
for (int j = i; j < n; j++) {
smax(y, svi[j][1]);
rmx[i][j] = y;
}
}
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = i; j < n; j++) {
Dodaj(svi[j][0], svi[j][1], 1);
cost[i][j] = Get(1, 0, N, svi[i][0], rmx[i][j]);
}
}
else {
Dodaj(svi[i - 1][0], svi[i - 1][1], -1);
for (int j = n - 1; j >= i; j--) {
cost[i][j] = Get(1, 0, N, svi[i][0], rmx[i][j]);
Dodaj(svi[j][0], svi[j][1], -1);
}
}
}
/*for (int i = 0; i < n; i++) {
int y = 0;
for (int j = i; j < n; j++) {
Dodaj(svi[j][0], svi[j][1], 1);
smax(y, svi[j][1]);
cost[i][j] = Get(1, 0, N, svi[i][0], y);
}
for (int j = i; j < n; j++) Dodaj(svi[j][0], svi[j][1], -1);
}*/
vector<int> dp(n);
while (d--) {
vector<int> ndp(n);
function<void(int, int, int, int)> Solve = [&] (int l, int r, int opl, int opr) {
if (l > r) return;
int best = 0;
int mid = l + r >> 1;
for (int j = opl; j <= min(opr, mid); j++) {
int x = cost[j][mid];
if (j > 0) x += dp[j - 1];
if (x >= ndp[mid]) {
ndp[mid] = x;
best = j;
}
}
Solve(l, mid - 1, opl, best);
Solve(mid + 1, r, best, opr);
};
Solve(0, n - 1, 0, n - 1);
swap(dp, ndp);
}
cout << ans - dp.back() << en;
return 0;
}
Compilation message
prison.cpp: In function 'void Add(int, int, int, int, int, int)':
prison.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = l + r >> 1;
| ~~^~~
prison.cpp: In function 'int Get(int, int, int, int, int)':
prison.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = l + r >> 1;
| ~~^~~
prison.cpp: In function 'int main()':
prison.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < svi.size(); i++) {
| ~~^~~~~~~~~~~~
prison.cpp: In lambda function:
prison.cpp:125:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
125 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
2380 KB |
Output is correct |
3 |
Correct |
8 ms |
2096 KB |
Output is correct |
4 |
Correct |
12 ms |
2516 KB |
Output is correct |
5 |
Correct |
16 ms |
2772 KB |
Output is correct |
6 |
Correct |
23 ms |
3412 KB |
Output is correct |
7 |
Correct |
20 ms |
3008 KB |
Output is correct |
8 |
Correct |
17 ms |
2568 KB |
Output is correct |
9 |
Correct |
17 ms |
2772 KB |
Output is correct |
10 |
Correct |
17 ms |
2612 KB |
Output is correct |
11 |
Correct |
16 ms |
2388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
59 ms |
10424 KB |
Output is correct |
3 |
Correct |
60 ms |
10140 KB |
Output is correct |
4 |
Correct |
53 ms |
10488 KB |
Output is correct |
5 |
Correct |
48 ms |
9376 KB |
Output is correct |
6 |
Correct |
51 ms |
8588 KB |
Output is correct |
7 |
Correct |
56 ms |
10828 KB |
Output is correct |
8 |
Correct |
54 ms |
8984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
2380 KB |
Output is correct |
3 |
Correct |
8 ms |
2096 KB |
Output is correct |
4 |
Correct |
12 ms |
2516 KB |
Output is correct |
5 |
Correct |
16 ms |
2772 KB |
Output is correct |
6 |
Correct |
23 ms |
3412 KB |
Output is correct |
7 |
Correct |
20 ms |
3008 KB |
Output is correct |
8 |
Correct |
17 ms |
2568 KB |
Output is correct |
9 |
Correct |
17 ms |
2772 KB |
Output is correct |
10 |
Correct |
17 ms |
2612 KB |
Output is correct |
11 |
Correct |
16 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
12 ms |
2388 KB |
Output is correct |
14 |
Correct |
9 ms |
2108 KB |
Output is correct |
15 |
Correct |
14 ms |
2492 KB |
Output is correct |
16 |
Correct |
16 ms |
2772 KB |
Output is correct |
17 |
Correct |
32 ms |
3336 KB |
Output is correct |
18 |
Correct |
25 ms |
2988 KB |
Output is correct |
19 |
Correct |
15 ms |
2532 KB |
Output is correct |
20 |
Correct |
16 ms |
2772 KB |
Output is correct |
21 |
Correct |
15 ms |
2644 KB |
Output is correct |
22 |
Correct |
12 ms |
2388 KB |
Output is correct |
23 |
Correct |
1316 ms |
44924 KB |
Output is correct |
24 |
Correct |
879 ms |
32796 KB |
Output is correct |
25 |
Correct |
1316 ms |
45140 KB |
Output is correct |
26 |
Correct |
869 ms |
32912 KB |
Output is correct |
27 |
Correct |
1294 ms |
45024 KB |
Output is correct |
28 |
Correct |
840 ms |
32808 KB |
Output is correct |
29 |
Correct |
1296 ms |
45212 KB |
Output is correct |
30 |
Correct |
650 ms |
26708 KB |
Output is correct |
31 |
Correct |
819 ms |
30988 KB |
Output is correct |
32 |
Correct |
590 ms |
25328 KB |
Output is correct |
33 |
Correct |
605 ms |
25680 KB |
Output is correct |
34 |
Correct |
1472 ms |
47976 KB |
Output is correct |
35 |
Correct |
1333 ms |
42528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
510 ms |
258012 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
2380 KB |
Output is correct |
3 |
Correct |
8 ms |
2096 KB |
Output is correct |
4 |
Correct |
12 ms |
2516 KB |
Output is correct |
5 |
Correct |
16 ms |
2772 KB |
Output is correct |
6 |
Correct |
23 ms |
3412 KB |
Output is correct |
7 |
Correct |
20 ms |
3008 KB |
Output is correct |
8 |
Correct |
17 ms |
2568 KB |
Output is correct |
9 |
Correct |
17 ms |
2772 KB |
Output is correct |
10 |
Correct |
17 ms |
2612 KB |
Output is correct |
11 |
Correct |
16 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
12 ms |
2388 KB |
Output is correct |
14 |
Correct |
9 ms |
2108 KB |
Output is correct |
15 |
Correct |
14 ms |
2492 KB |
Output is correct |
16 |
Correct |
16 ms |
2772 KB |
Output is correct |
17 |
Correct |
32 ms |
3336 KB |
Output is correct |
18 |
Correct |
25 ms |
2988 KB |
Output is correct |
19 |
Correct |
15 ms |
2532 KB |
Output is correct |
20 |
Correct |
16 ms |
2772 KB |
Output is correct |
21 |
Correct |
15 ms |
2644 KB |
Output is correct |
22 |
Correct |
12 ms |
2388 KB |
Output is correct |
23 |
Correct |
1316 ms |
44924 KB |
Output is correct |
24 |
Correct |
879 ms |
32796 KB |
Output is correct |
25 |
Correct |
1316 ms |
45140 KB |
Output is correct |
26 |
Correct |
869 ms |
32912 KB |
Output is correct |
27 |
Correct |
1294 ms |
45024 KB |
Output is correct |
28 |
Correct |
840 ms |
32808 KB |
Output is correct |
29 |
Correct |
1296 ms |
45212 KB |
Output is correct |
30 |
Correct |
650 ms |
26708 KB |
Output is correct |
31 |
Correct |
819 ms |
30988 KB |
Output is correct |
32 |
Correct |
590 ms |
25328 KB |
Output is correct |
33 |
Correct |
605 ms |
25680 KB |
Output is correct |
34 |
Correct |
1472 ms |
47976 KB |
Output is correct |
35 |
Correct |
1333 ms |
42528 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Runtime error |
510 ms |
258012 KB |
Execution killed with signal 11 |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
2380 KB |
Output is correct |
3 |
Correct |
8 ms |
2096 KB |
Output is correct |
4 |
Correct |
12 ms |
2516 KB |
Output is correct |
5 |
Correct |
16 ms |
2772 KB |
Output is correct |
6 |
Correct |
23 ms |
3412 KB |
Output is correct |
7 |
Correct |
20 ms |
3008 KB |
Output is correct |
8 |
Correct |
17 ms |
2568 KB |
Output is correct |
9 |
Correct |
17 ms |
2772 KB |
Output is correct |
10 |
Correct |
17 ms |
2612 KB |
Output is correct |
11 |
Correct |
16 ms |
2388 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
59 ms |
10424 KB |
Output is correct |
14 |
Correct |
60 ms |
10140 KB |
Output is correct |
15 |
Correct |
53 ms |
10488 KB |
Output is correct |
16 |
Correct |
48 ms |
9376 KB |
Output is correct |
17 |
Correct |
51 ms |
8588 KB |
Output is correct |
18 |
Correct |
56 ms |
10828 KB |
Output is correct |
19 |
Correct |
54 ms |
8984 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
12 ms |
2388 KB |
Output is correct |
22 |
Correct |
9 ms |
2108 KB |
Output is correct |
23 |
Correct |
14 ms |
2492 KB |
Output is correct |
24 |
Correct |
16 ms |
2772 KB |
Output is correct |
25 |
Correct |
32 ms |
3336 KB |
Output is correct |
26 |
Correct |
25 ms |
2988 KB |
Output is correct |
27 |
Correct |
15 ms |
2532 KB |
Output is correct |
28 |
Correct |
16 ms |
2772 KB |
Output is correct |
29 |
Correct |
15 ms |
2644 KB |
Output is correct |
30 |
Correct |
12 ms |
2388 KB |
Output is correct |
31 |
Correct |
1316 ms |
44924 KB |
Output is correct |
32 |
Correct |
879 ms |
32796 KB |
Output is correct |
33 |
Correct |
1316 ms |
45140 KB |
Output is correct |
34 |
Correct |
869 ms |
32912 KB |
Output is correct |
35 |
Correct |
1294 ms |
45024 KB |
Output is correct |
36 |
Correct |
840 ms |
32808 KB |
Output is correct |
37 |
Correct |
1296 ms |
45212 KB |
Output is correct |
38 |
Correct |
650 ms |
26708 KB |
Output is correct |
39 |
Correct |
819 ms |
30988 KB |
Output is correct |
40 |
Correct |
590 ms |
25328 KB |
Output is correct |
41 |
Correct |
605 ms |
25680 KB |
Output is correct |
42 |
Correct |
1472 ms |
47976 KB |
Output is correct |
43 |
Correct |
1333 ms |
42528 KB |
Output is correct |
44 |
Correct |
1 ms |
212 KB |
Output is correct |
45 |
Runtime error |
510 ms |
258012 KB |
Execution killed with signal 11 |
46 |
Halted |
0 ms |
0 KB |
- |