oj.uz

Submission #577166

# Submission time Handle Problem Language Result Execution time Memory
577166 2022-06-14T08:17:10 Z amunduzbaev Tortoise (CEOI21_tortoise) C++17
0 / 100
 156 ms 294476 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[2][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] = 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[0][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[0][i][x] = min(dp[0][i][x], *ss.begin() + x * 2 * min(l[i], r[i]));
					}
					
					if(*ss.begin() + (x - 1) * 2 * min(l[i], r[i]) <= 2 * i){
						dp[1][i][x] = min(dp[1][i][x], *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], dp[1][i][x] + r[i]);
					}
				}
			}
			
			if(a[i] == -1) dp[0][i][x] = min(dp[0][i][x], dp[1][i][x]);
			if(i + r[i] < N) dp[0][i][x] = min(dp[0][i][x], back[i + r[i]][x] + r[i]);
			dp[0][i+1][x] = min(dp[0][i+1][x], dp[0][i][x] + 1);
			dp[1][i+1][x] = min(dp[1][i+1][x], dp[1][i][x] + 1);
			if(dp[0][i][x] < inf || dp[1][i][x] < inf){
				//~ cout<<i<<" "<<x<<" "<<dp[0][i][x]<<" "<<dp[1][i][x]<<endl;
				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 123 ms 294420 KB Output is correct
2 Correct 133 ms 294416 KB Output is correct
3 Correct 155 ms 294408 KB Output is correct
4 Correct 145 ms 294392 KB Output is correct
5 Correct 131 ms 294412 KB Output is correct
6 Correct 156 ms 294444 KB Output is correct
7 Correct 131 ms 294404 KB Output is correct
8 Correct 132 ms 294472 KB Output is correct
9 Correct 130 ms 294368 KB Output is correct
10 Correct 136 ms 294392 KB Output is correct
11 Correct 126 ms 294452 KB Output is correct
12 Correct 118 ms 294392 KB Output is correct
13 Correct 122 ms 294440 KB Output is correct
14 Correct 142 ms 294476 KB Output is correct
15 Correct 131 ms 294460 KB Output is correct
16 Incorrect 134 ms 294404 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 294420 KB Output is correct
2 Correct 133 ms 294416 KB Output is correct
3 Correct 155 ms 294408 KB Output is correct
4 Correct 145 ms 294392 KB Output is correct
5 Correct 131 ms 294412 KB Output is correct
6 Correct 156 ms 294444 KB Output is correct
7 Correct 131 ms 294404 KB Output is correct
8 Correct 132 ms 294472 KB Output is correct
9 Correct 130 ms 294368 KB Output is correct
10 Correct 136 ms 294392 KB Output is correct
11 Correct 126 ms 294452 KB Output is correct
12 Correct 118 ms 294392 KB Output is correct
13 Correct 122 ms 294440 KB Output is correct
14 Correct 142 ms 294476 KB Output is correct
15 Correct 131 ms 294460 KB Output is correct
16 Incorrect 134 ms 294404 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 294420 KB Output is correct
2 Correct 133 ms 294416 KB Output is correct
3 Correct 155 ms 294408 KB Output is correct
4 Correct 145 ms 294392 KB Output is correct
5 Correct 131 ms 294412 KB Output is correct
6 Correct 156 ms 294444 KB Output is correct
7 Correct 131 ms 294404 KB Output is correct
8 Correct 132 ms 294472 KB Output is correct
9 Correct 130 ms 294368 KB Output is correct
10 Correct 136 ms 294392 KB Output is correct
11 Correct 126 ms 294452 KB Output is correct
12 Correct 118 ms 294392 KB Output is correct
13 Correct 122 ms 294440 KB Output is correct
14 Correct 142 ms 294476 KB Output is correct
15 Correct 131 ms 294460 KB Output is correct
16 Incorrect 134 ms 294404 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 294420 KB Output is correct
2 Correct 133 ms 294416 KB Output is correct
3 Correct 155 ms 294408 KB Output is correct
4 Correct 145 ms 294392 KB Output is correct
5 Correct 131 ms 294412 KB Output is correct
6 Correct 156 ms 294444 KB Output is correct
7 Correct 131 ms 294404 KB Output is correct
8 Correct 132 ms 294472 KB Output is correct
9 Correct 130 ms 294368 KB Output is correct
10 Correct 136 ms 294392 KB Output is correct
11 Correct 126 ms 294452 KB Output is correct
12 Correct 118 ms 294392 KB Output is correct
13 Correct 122 ms 294440 KB Output is correct
14 Correct 142 ms 294476 KB Output is correct
15 Correct 131 ms 294460 KB Output is correct
16 Incorrect 134 ms 294404 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 294420 KB Output is correct
2 Correct 133 ms 294416 KB Output is correct
3 Correct 155 ms 294408 KB Output is correct
4 Correct 145 ms 294392 KB Output is correct
5 Correct 131 ms 294412 KB Output is correct
6 Correct 156 ms 294444 KB Output is correct
7 Correct 131 ms 294404 KB Output is correct
8 Correct 132 ms 294472 KB Output is correct
9 Correct 130 ms 294368 KB Output is correct
10 Correct 136 ms 294392 KB Output is correct
11 Correct 126 ms 294452 KB Output is correct
12 Correct 118 ms 294392 KB Output is correct
13 Correct 122 ms 294440 KB Output is correct
14 Correct 142 ms 294476 KB Output is correct
15 Correct 131 ms 294460 KB Output is correct
16 Incorrect 134 ms 294404 KB Output isn't correct
17 Halted 0 ms 0 KB -