oj.uz

Submission #577167

# Submission time Handle Problem Language Result Execution time Memory
577167 2022-06-14T08:21:17 Z amunduzbaev Tortoise (CEOI21_tortoise) C++17
0 / 100
 79 ms 196436 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int int64_t

const int N = 5005;
const int inf = 1e9;
int dp[N][N], old[N][N], a[N];
int l[N], r[N], back[N][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=0;i<n;i++){
		l[i] = n;
		cin>>a[i];
		if(a[i] == -1) l[i] = 0;
		else if(i) l[i] = l[i-1] + 1;
	}
	for(int i=n-1;~i;i--){
		r[i] = n;
		if(a[i] == -1) r[i] = 0;
		else if(i + 1 < n) r[i] = r[i+1] + 1;
	}
	
	memset(dp, 63, sizeof dp);
	//~ cout<<dp[0][0][0]<<"\n";
	//~ cout<<inf<<"\n";
	memset(back, 63, sizeof back);
	dp[0][0] = 0;
	int res = 0;
	for(int i=0;i<=n;i++){
		multiset<int> ss;
		for(int x=0;x<=n;x++){
			if(a[i] > 0){
				old[i][x] = dp[i][x] - x * 2 * min(l[i], r[i]);
				ss.insert(old[i][x]);
				if(x){
					if(*ss.begin() + (x - 1) * 2 * min(l[i], r[i])<= 2 * i){
						dp[i][x] = min(dp[i][x], *ss.begin() + x * 2 * min(l[i], r[i]));
					}
					
					int tmp = inf;
					if(*ss.begin() + (x - 1) * 2 * min(l[i], r[i]) <= 2 * i){
						tmp = *ss.begin() + (x - 1) * 2 * min(l[i], r[i]);
					}
					if(x >= a[i]){
						ss.erase(ss.find(old[i][x - a[i]]));
					}
					
					if(i + r[i] < N){
						back[i + r[i]][x] = min(back[i + r[i]][x], tmp + r[i]);
					}
				}
			}
			
			if(i + r[i] < N) dp[i][x] = min(dp[i][x], back[i + r[i]][x] + r[i]);
			dp[i+1][x] = min(dp[i+1][x], dp[i][x] + 1);
			if(dp[i][x] < inf){
				res = max(res, x);
			}
		}
	}
	
	int tot = 0;
	for(int i=0;i<n;i++){
		if(~a[i]) tot += a[i];
	}
	
	cout<<tot - res<<"\n";
}

/*

6
-1 0 0 1 1 -1

*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 196340 KB Output is correct
2 Correct 78 ms 196424 KB Output is correct
3 Correct 76 ms 196436 KB Output is correct
4 Correct 73 ms 196356 KB Output is correct
5 Correct 73 ms 196352 KB Output is correct
6 Correct 79 ms 196416 KB Output is correct
7 Correct 70 ms 196332 KB Output is correct
8 Correct 74 ms 196428 KB Output is correct
9 Correct 69 ms 196368 KB Output is correct
10 Correct 73 ms 196320 KB Output is correct
11 Correct 72 ms 196324 KB Output is correct
12 Correct 72 ms 196364 KB Output is correct
13 Correct 73 ms 196316 KB Output is correct
14 Correct 72 ms 196304 KB Output is correct
15 Correct 71 ms 196432 KB Output is correct
16 Incorrect 71 ms 196424 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 196340 KB Output is correct
2 Correct 78 ms 196424 KB Output is correct
3 Correct 76 ms 196436 KB Output is correct
4 Correct 73 ms 196356 KB Output is correct
5 Correct 73 ms 196352 KB Output is correct
6 Correct 79 ms 196416 KB Output is correct
7 Correct 70 ms 196332 KB Output is correct
8 Correct 74 ms 196428 KB Output is correct
9 Correct 69 ms 196368 KB Output is correct
10 Correct 73 ms 196320 KB Output is correct
11 Correct 72 ms 196324 KB Output is correct
12 Correct 72 ms 196364 KB Output is correct
13 Correct 73 ms 196316 KB Output is correct
14 Correct 72 ms 196304 KB Output is correct
15 Correct 71 ms 196432 KB Output is correct
16 Incorrect 71 ms 196424 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 196340 KB Output is correct
2 Correct 78 ms 196424 KB Output is correct
3 Correct 76 ms 196436 KB Output is correct
4 Correct 73 ms 196356 KB Output is correct
5 Correct 73 ms 196352 KB Output is correct
6 Correct 79 ms 196416 KB Output is correct
7 Correct 70 ms 196332 KB Output is correct
8 Correct 74 ms 196428 KB Output is correct
9 Correct 69 ms 196368 KB Output is correct
10 Correct 73 ms 196320 KB Output is correct
11 Correct 72 ms 196324 KB Output is correct
12 Correct 72 ms 196364 KB Output is correct
13 Correct 73 ms 196316 KB Output is correct
14 Correct 72 ms 196304 KB Output is correct
15 Correct 71 ms 196432 KB Output is correct
16 Incorrect 71 ms 196424 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 196340 KB Output is correct
2 Correct 78 ms 196424 KB Output is correct
3 Correct 76 ms 196436 KB Output is correct
4 Correct 73 ms 196356 KB Output is correct
5 Correct 73 ms 196352 KB Output is correct
6 Correct 79 ms 196416 KB Output is correct
7 Correct 70 ms 196332 KB Output is correct
8 Correct 74 ms 196428 KB Output is correct
9 Correct 69 ms 196368 KB Output is correct
10 Correct 73 ms 196320 KB Output is correct
11 Correct 72 ms 196324 KB Output is correct
12 Correct 72 ms 196364 KB Output is correct
13 Correct 73 ms 196316 KB Output is correct
14 Correct 72 ms 196304 KB Output is correct
15 Correct 71 ms 196432 KB Output is correct
16 Incorrect 71 ms 196424 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 196340 KB Output is correct
2 Correct 78 ms 196424 KB Output is correct
3 Correct 76 ms 196436 KB Output is correct
4 Correct 73 ms 196356 KB Output is correct
5 Correct 73 ms 196352 KB Output is correct
6 Correct 79 ms 196416 KB Output is correct
7 Correct 70 ms 196332 KB Output is correct
8 Correct 74 ms 196428 KB Output is correct
9 Correct 69 ms 196368 KB Output is correct
10 Correct 73 ms 196320 KB Output is correct
11 Correct 72 ms 196324 KB Output is correct
12 Correct 72 ms 196364 KB Output is correct
13 Correct 73 ms 196316 KB Output is correct
14 Correct 72 ms 196304 KB Output is correct
15 Correct 71 ms 196432 KB Output is correct
16 Incorrect 71 ms 196424 KB Output isn't correct
17 Halted 0 ms 0 KB -