#include<bits/stdc++.h>
#define MAXN 5007
using namespace std;
int n,a[MAXN];
int dist[MAXN],last,sum,nxt[MAXN];
int dp[MAXN][2*MAXN][2];
bool li[MAXN][2*MAXN][2];
int ff(int pos,int tim,int c){
if(tim>2*n or pos>n)return 0;
return dp[pos][tim][c];
}
struct Fenwick{
int fenwick[MAXN];
void update(int x,int val){
while(x<=n){
fenwick[x]=max(fenwick[x],val);
x+=(x & (-x));
}
}
int getmax(int x){
int res=0;
while(x>=1){
res=max(res,fenwick[x]);
x-=(x & (-x));
}
return res;
}
};
Fenwick fen[3*MAXN];
void calcdp(){
for(int pos=n;pos>=1;pos--){
for(int tim=2*n;tim>=0;tim--){
for(int c=1;c>=0;c--){
if(c==1){
if(nxt[pos]==2*n)dp[pos][tim][c]=0;
else{
if(tim+2*nxt[pos]-pos>3*n)dp[pos][tim][c]=1;
else dp[pos][tim][c]=fen[tim+2*nxt[pos]-pos].getmax(nxt[pos])+1;
}
}else{
if(a[pos]>0){
if(tim<=2*(pos-1))dp[pos][tim][c]=max(dp[pos][tim][c],ff(pos,tim,1));
for(int s=0;tim+s*2*dist[pos]<=2*(pos-1) and s+1<=a[pos];s++){
dp[pos][tim][c]=max(dp[pos][tim][c],ff(pos+1,tim+(s+1)*2*dist[pos]+1,0)+s+1);
if(s+1<a[pos] and tim+2*(s+1)*dist[pos]<=2*(pos-1))dp[pos][tim][c]=max(dp[pos][tim][c], ff(pos,tim+(s+1)*2*dist[pos],1)+s+1);
}
}
if(pos<n)dp[pos][tim][c]=max(dp[pos][tim][c],ff(pos+1,tim+1,c));
}
}
}
for(int tim=2*n;tim>=0;tim--){
fen[pos+tim].update(pos,dp[pos][tim][0]);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dist[i]=n;
if(a[i]>=0)sum+=a[i];
}
last=-n;
for(int i=1;i<=n;i++){
if(a[i]==-1)last=i;
dist[i]=min(dist[i],i-last);
}
last=2*n;
for(int i=n;i>=1;i--){
if(a[i]==-1)last=i;
dist[i]=min(dist[i],last-i);
nxt[i]=last;
}
calcdp();
cout<<sum-dp[1][0][0]<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
5976 KB |
Output is correct |
28 |
Correct |
10 ms |
7260 KB |
Output is correct |
29 |
Correct |
6 ms |
6748 KB |
Output is correct |
30 |
Correct |
5 ms |
5980 KB |
Output is correct |
31 |
Correct |
5 ms |
7260 KB |
Output is correct |
32 |
Correct |
5 ms |
4956 KB |
Output is correct |
33 |
Correct |
7 ms |
6748 KB |
Output is correct |
34 |
Correct |
4 ms |
5980 KB |
Output is correct |
35 |
Correct |
7 ms |
7516 KB |
Output is correct |
36 |
Correct |
6 ms |
7516 KB |
Output is correct |
37 |
Correct |
7 ms |
7388 KB |
Output is correct |
38 |
Correct |
6 ms |
7512 KB |
Output is correct |
39 |
Correct |
7 ms |
7448 KB |
Output is correct |
40 |
Correct |
6 ms |
7516 KB |
Output is correct |
41 |
Correct |
9 ms |
7372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
5976 KB |
Output is correct |
28 |
Correct |
10 ms |
7260 KB |
Output is correct |
29 |
Correct |
6 ms |
6748 KB |
Output is correct |
30 |
Correct |
5 ms |
5980 KB |
Output is correct |
31 |
Correct |
5 ms |
7260 KB |
Output is correct |
32 |
Correct |
5 ms |
4956 KB |
Output is correct |
33 |
Correct |
7 ms |
6748 KB |
Output is correct |
34 |
Correct |
4 ms |
5980 KB |
Output is correct |
35 |
Correct |
7 ms |
7516 KB |
Output is correct |
36 |
Correct |
6 ms |
7516 KB |
Output is correct |
37 |
Correct |
7 ms |
7388 KB |
Output is correct |
38 |
Correct |
6 ms |
7512 KB |
Output is correct |
39 |
Correct |
7 ms |
7448 KB |
Output is correct |
40 |
Correct |
6 ms |
7516 KB |
Output is correct |
41 |
Correct |
9 ms |
7372 KB |
Output is correct |
42 |
Correct |
3 ms |
4700 KB |
Output is correct |
43 |
Correct |
3 ms |
4700 KB |
Output is correct |
44 |
Correct |
4 ms |
5724 KB |
Output is correct |
45 |
Correct |
6 ms |
7004 KB |
Output is correct |
46 |
Correct |
4 ms |
5380 KB |
Output is correct |
47 |
Correct |
4 ms |
4596 KB |
Output is correct |
48 |
Correct |
5 ms |
6236 KB |
Output is correct |
49 |
Correct |
5 ms |
5288 KB |
Output is correct |
50 |
Correct |
9 ms |
6656 KB |
Output is correct |
51 |
Correct |
7 ms |
7000 KB |
Output is correct |
52 |
Correct |
5 ms |
4956 KB |
Output is correct |
53 |
Correct |
11 ms |
6900 KB |
Output is correct |
54 |
Correct |
11 ms |
6744 KB |
Output is correct |
55 |
Correct |
7 ms |
5980 KB |
Output is correct |
56 |
Correct |
6 ms |
7260 KB |
Output is correct |
57 |
Correct |
6 ms |
4700 KB |
Output is correct |
58 |
Correct |
6 ms |
6748 KB |
Output is correct |
59 |
Correct |
4 ms |
5184 KB |
Output is correct |
60 |
Correct |
6 ms |
6236 KB |
Output is correct |
61 |
Correct |
5 ms |
6668 KB |
Output is correct |
62 |
Correct |
6 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
5976 KB |
Output is correct |
28 |
Correct |
10 ms |
7260 KB |
Output is correct |
29 |
Correct |
6 ms |
6748 KB |
Output is correct |
30 |
Correct |
5 ms |
5980 KB |
Output is correct |
31 |
Correct |
5 ms |
7260 KB |
Output is correct |
32 |
Correct |
5 ms |
4956 KB |
Output is correct |
33 |
Correct |
7 ms |
6748 KB |
Output is correct |
34 |
Correct |
4 ms |
5980 KB |
Output is correct |
35 |
Correct |
7 ms |
7516 KB |
Output is correct |
36 |
Correct |
6 ms |
7516 KB |
Output is correct |
37 |
Correct |
7 ms |
7388 KB |
Output is correct |
38 |
Correct |
6 ms |
7512 KB |
Output is correct |
39 |
Correct |
7 ms |
7448 KB |
Output is correct |
40 |
Correct |
6 ms |
7516 KB |
Output is correct |
41 |
Correct |
9 ms |
7372 KB |
Output is correct |
42 |
Correct |
3 ms |
4700 KB |
Output is correct |
43 |
Correct |
3 ms |
4700 KB |
Output is correct |
44 |
Correct |
4 ms |
5724 KB |
Output is correct |
45 |
Correct |
6 ms |
7004 KB |
Output is correct |
46 |
Correct |
4 ms |
5380 KB |
Output is correct |
47 |
Correct |
4 ms |
4596 KB |
Output is correct |
48 |
Correct |
5 ms |
6236 KB |
Output is correct |
49 |
Correct |
5 ms |
5288 KB |
Output is correct |
50 |
Correct |
9 ms |
6656 KB |
Output is correct |
51 |
Correct |
7 ms |
7000 KB |
Output is correct |
52 |
Correct |
5 ms |
4956 KB |
Output is correct |
53 |
Correct |
11 ms |
6900 KB |
Output is correct |
54 |
Correct |
11 ms |
6744 KB |
Output is correct |
55 |
Correct |
7 ms |
5980 KB |
Output is correct |
56 |
Correct |
6 ms |
7260 KB |
Output is correct |
57 |
Correct |
6 ms |
4700 KB |
Output is correct |
58 |
Correct |
6 ms |
6748 KB |
Output is correct |
59 |
Correct |
4 ms |
5184 KB |
Output is correct |
60 |
Correct |
6 ms |
6236 KB |
Output is correct |
61 |
Correct |
5 ms |
6668 KB |
Output is correct |
62 |
Correct |
6 ms |
6748 KB |
Output is correct |
63 |
Runtime error |
1834 ms |
524288 KB |
Execution killed with signal 9 |
64 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
0 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
5976 KB |
Output is correct |
28 |
Correct |
10 ms |
7260 KB |
Output is correct |
29 |
Correct |
6 ms |
6748 KB |
Output is correct |
30 |
Correct |
5 ms |
5980 KB |
Output is correct |
31 |
Correct |
5 ms |
7260 KB |
Output is correct |
32 |
Correct |
5 ms |
4956 KB |
Output is correct |
33 |
Correct |
7 ms |
6748 KB |
Output is correct |
34 |
Correct |
4 ms |
5980 KB |
Output is correct |
35 |
Correct |
7 ms |
7516 KB |
Output is correct |
36 |
Correct |
6 ms |
7516 KB |
Output is correct |
37 |
Correct |
7 ms |
7388 KB |
Output is correct |
38 |
Correct |
6 ms |
7512 KB |
Output is correct |
39 |
Correct |
7 ms |
7448 KB |
Output is correct |
40 |
Correct |
6 ms |
7516 KB |
Output is correct |
41 |
Correct |
9 ms |
7372 KB |
Output is correct |
42 |
Correct |
3 ms |
4700 KB |
Output is correct |
43 |
Correct |
3 ms |
4700 KB |
Output is correct |
44 |
Correct |
4 ms |
5724 KB |
Output is correct |
45 |
Correct |
6 ms |
7004 KB |
Output is correct |
46 |
Correct |
4 ms |
5380 KB |
Output is correct |
47 |
Correct |
4 ms |
4596 KB |
Output is correct |
48 |
Correct |
5 ms |
6236 KB |
Output is correct |
49 |
Correct |
5 ms |
5288 KB |
Output is correct |
50 |
Correct |
9 ms |
6656 KB |
Output is correct |
51 |
Correct |
7 ms |
7000 KB |
Output is correct |
52 |
Correct |
5 ms |
4956 KB |
Output is correct |
53 |
Correct |
11 ms |
6900 KB |
Output is correct |
54 |
Correct |
11 ms |
6744 KB |
Output is correct |
55 |
Correct |
7 ms |
5980 KB |
Output is correct |
56 |
Correct |
6 ms |
7260 KB |
Output is correct |
57 |
Correct |
6 ms |
4700 KB |
Output is correct |
58 |
Correct |
6 ms |
6748 KB |
Output is correct |
59 |
Correct |
4 ms |
5184 KB |
Output is correct |
60 |
Correct |
6 ms |
6236 KB |
Output is correct |
61 |
Correct |
5 ms |
6668 KB |
Output is correct |
62 |
Correct |
6 ms |
6748 KB |
Output is correct |
63 |
Runtime error |
1834 ms |
524288 KB |
Execution killed with signal 9 |
64 |
Halted |
0 ms |
0 KB |
- |