#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF=1e9;
const int N=4010, D=4010;
int n, d, T, r[N], mx[N], dp[N][D], t[4*N][D], lazy[4*N][D];
void push(int id, int in)
{
t[id][in]+=lazy[id][in];
if(id*2+1<4*N){
lazy[id*2][in]+=lazy[id][in];
lazy[id*2+1][in]+=lazy[id][in];
}
// else if(id*2<4*N){
// lazy[id*2][in]+=lazy[id][in];
// }
lazy[id][in]=0;
}
void add(int x, int y, int in, int val, int l=0, int r=n, int id=1)
{
push(id, in);
if(r<x||l>y) return;
if(x<=l&&r<=y){
lazy[id][in]+=val;
push(id, in);
return;
}
int m=(l+r)/2;
add(x, y, in, val, l, m, id*2);
add(x, y, in, val, m+1, r, id*2+1);
t[id][in]=min(t[id*2][in], t[id*2+1][in]);
}
int get(int x, int y, int in, int l=0, int r=n, int id=1)
{
push(id, in);
if(r<x||l>y) return INF;
if(x<=l&&r<=y) return t[id][in];
int m=(l+r)/2;
int k=min(get(x, y, in, l, m, id*2), get(x, y, in, m+1, r, id*2+1));
t[id][in]=min(t[id*2][in], t[id*2+1][in]);
return k;
}
vector<pii> inf;
void build()
{
FOR(i, 1, n+1) mx[i]=-1;
sort(inf.begin(), inf.end());
set<int, greater<int>> st;
for(int i=n; i>=1; i--){
while(!inf.empty() && (inf.back()).f==i){
pii u=inf.back(); inf.pop_back();
st.insert(u.s);
}
if(!st.empty()){
mx[i]=*st.begin();
}
st.erase(i);
}
}
int main()
{
FAST_IO;
cin >> n >> d >> T;
FOR(i, 1, n+1)
{
int t; cin >> t;
if(t>T) r[i]=-1;
else r[i]=min(n, i+T-t);
inf.pb({r[i],i});
}
build();
FOR(i, 0, n+1) FOR(j, 0, d+2) dp[i][j]=INF;
// FOR(i, 0, 4*N) FOR(j, 0, D) t[i][j]=INF;
dp[0][0]=0;
// FOR(i, 1, n+1)
// {
// cout << mx[i] << " ";
// }
// cout << '\n';
FOR(i, 1, n+1)
{
if(mx[i]!=-1) add(0, 0, 0, 1);
dp[i][1]=min(dp[i][1], get(0, 0, 0));
add(i, i, 1, dp[i][1]);
// cout << i << " " << dp[i][1] << '\n';
FOR(j, 2, d+2)
{
if(mx[i]!=-1) add(0, mx[i]-1, j-1, 1);
dp[i][j]=min(dp[i][j], get(0, i-1, j-1));
dp[i][j]=min(dp[i][j], dp[i][j-1]);
add(i, i, j, dp[i][j]);
}
}
// assert(dp[n][d+1]!=INF);
//
cout << dp[n][d+1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
7 ms |
26536 KB |
Output is correct |
3 |
Correct |
9 ms |
28252 KB |
Output is correct |
4 |
Correct |
21 ms |
29684 KB |
Output is correct |
5 |
Correct |
24 ms |
27092 KB |
Output is correct |
6 |
Correct |
8 ms |
27736 KB |
Output is correct |
7 |
Correct |
13 ms |
27996 KB |
Output is correct |
8 |
Correct |
8 ms |
27596 KB |
Output is correct |
9 |
Correct |
10 ms |
27880 KB |
Output is correct |
10 |
Correct |
15 ms |
28252 KB |
Output is correct |
11 |
Correct |
23 ms |
28760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
7 ms |
26536 KB |
Output is correct |
3 |
Correct |
9 ms |
28252 KB |
Output is correct |
4 |
Correct |
21 ms |
29684 KB |
Output is correct |
5 |
Correct |
24 ms |
27092 KB |
Output is correct |
6 |
Correct |
8 ms |
27736 KB |
Output is correct |
7 |
Correct |
13 ms |
27996 KB |
Output is correct |
8 |
Correct |
8 ms |
27596 KB |
Output is correct |
9 |
Correct |
10 ms |
27880 KB |
Output is correct |
10 |
Correct |
15 ms |
28252 KB |
Output is correct |
11 |
Correct |
23 ms |
28760 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
7 ms |
26652 KB |
Output is correct |
14 |
Correct |
8 ms |
23640 KB |
Output is correct |
15 |
Correct |
16 ms |
28252 KB |
Output is correct |
16 |
Correct |
24 ms |
28692 KB |
Output is correct |
17 |
Correct |
7 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27992 KB |
Output is correct |
19 |
Correct |
8 ms |
27740 KB |
Output is correct |
20 |
Correct |
10 ms |
27740 KB |
Output is correct |
21 |
Correct |
15 ms |
28252 KB |
Output is correct |
22 |
Correct |
23 ms |
28764 KB |
Output is correct |
23 |
Correct |
243 ms |
134684 KB |
Output is correct |
24 |
Correct |
426 ms |
145120 KB |
Output is correct |
25 |
Correct |
639 ms |
155804 KB |
Output is correct |
26 |
Correct |
895 ms |
166104 KB |
Output is correct |
27 |
Correct |
1139 ms |
176548 KB |
Output is correct |
28 |
Correct |
182 ms |
130604 KB |
Output is correct |
29 |
Correct |
240 ms |
130260 KB |
Output is correct |
30 |
Correct |
249 ms |
136700 KB |
Output is correct |
31 |
Correct |
480 ms |
150288 KB |
Output is correct |
32 |
Correct |
269 ms |
136784 KB |
Output is correct |
33 |
Correct |
264 ms |
135280 KB |
Output is correct |
34 |
Correct |
145 ms |
126676 KB |
Output is correct |
35 |
Correct |
1041 ms |
174036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
7 ms |
26536 KB |
Output is correct |
3 |
Correct |
9 ms |
28252 KB |
Output is correct |
4 |
Correct |
21 ms |
29684 KB |
Output is correct |
5 |
Correct |
24 ms |
27092 KB |
Output is correct |
6 |
Correct |
8 ms |
27736 KB |
Output is correct |
7 |
Correct |
13 ms |
27996 KB |
Output is correct |
8 |
Correct |
8 ms |
27596 KB |
Output is correct |
9 |
Correct |
10 ms |
27880 KB |
Output is correct |
10 |
Correct |
15 ms |
28252 KB |
Output is correct |
11 |
Correct |
23 ms |
28760 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
7 ms |
26652 KB |
Output is correct |
14 |
Correct |
8 ms |
23640 KB |
Output is correct |
15 |
Correct |
16 ms |
28252 KB |
Output is correct |
16 |
Correct |
24 ms |
28692 KB |
Output is correct |
17 |
Correct |
7 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27992 KB |
Output is correct |
19 |
Correct |
8 ms |
27740 KB |
Output is correct |
20 |
Correct |
10 ms |
27740 KB |
Output is correct |
21 |
Correct |
15 ms |
28252 KB |
Output is correct |
22 |
Correct |
23 ms |
28764 KB |
Output is correct |
23 |
Correct |
243 ms |
134684 KB |
Output is correct |
24 |
Correct |
426 ms |
145120 KB |
Output is correct |
25 |
Correct |
639 ms |
155804 KB |
Output is correct |
26 |
Correct |
895 ms |
166104 KB |
Output is correct |
27 |
Correct |
1139 ms |
176548 KB |
Output is correct |
28 |
Correct |
182 ms |
130604 KB |
Output is correct |
29 |
Correct |
240 ms |
130260 KB |
Output is correct |
30 |
Correct |
249 ms |
136700 KB |
Output is correct |
31 |
Correct |
480 ms |
150288 KB |
Output is correct |
32 |
Correct |
269 ms |
136784 KB |
Output is correct |
33 |
Correct |
264 ms |
135280 KB |
Output is correct |
34 |
Correct |
145 ms |
126676 KB |
Output is correct |
35 |
Correct |
1041 ms |
174036 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
7 ms |
26536 KB |
Output is correct |
3 |
Correct |
9 ms |
28252 KB |
Output is correct |
4 |
Correct |
21 ms |
29684 KB |
Output is correct |
5 |
Correct |
24 ms |
27092 KB |
Output is correct |
6 |
Correct |
8 ms |
27736 KB |
Output is correct |
7 |
Correct |
13 ms |
27996 KB |
Output is correct |
8 |
Correct |
8 ms |
27596 KB |
Output is correct |
9 |
Correct |
10 ms |
27880 KB |
Output is correct |
10 |
Correct |
15 ms |
28252 KB |
Output is correct |
11 |
Correct |
23 ms |
28760 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |