oj.uz

Submission #577169

# Submission time Handle Problem Language Result Execution time Memory
577169 2022-06-14T08:24:27 Z amunduzbaev Tortoise (CEOI21_tortoise) C++17
0 / 100
 91 ms 196428 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);
	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]);
				if(x){
					int tmp = inf;
					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]));
						tmp = *ss.begin() + (x - 1) * 2 * min(l[i], r[i]);
					}
					
					if(i + r[i] < N){
						back[i + r[i]][x] = min(back[i + r[i]][x], tmp + r[i]);
					}
				}
				ss.insert(old[i][x]);
				if(x >= a[i]){
					ss.erase(ss.find(old[i][x - a[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 75 ms 196420 KB Output is correct
2 Correct 72 ms 196356 KB Output is correct
3 Correct 76 ms 196336 KB Output is correct
4 Correct 74 ms 196380 KB Output is correct
5 Correct 71 ms 196428 KB Output is correct
6 Correct 75 ms 196340 KB Output is correct
7 Correct 70 ms 196404 KB Output is correct
8 Correct 83 ms 196420 KB Output is correct
9 Correct 79 ms 196404 KB Output is correct
10 Correct 69 ms 196304 KB Output is correct
11 Correct 69 ms 196308 KB Output is correct
12 Correct 70 ms 196412 KB Output is correct
13 Correct 71 ms 196360 KB Output is correct
14 Correct 91 ms 196304 KB Output is correct
15 Correct 72 ms 196428 KB Output is correct
16 Incorrect 73 ms 196392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196420 KB Output is correct
2 Correct 72 ms 196356 KB Output is correct
3 Correct 76 ms 196336 KB Output is correct
4 Correct 74 ms 196380 KB Output is correct
5 Correct 71 ms 196428 KB Output is correct
6 Correct 75 ms 196340 KB Output is correct
7 Correct 70 ms 196404 KB Output is correct
8 Correct 83 ms 196420 KB Output is correct
9 Correct 79 ms 196404 KB Output is correct
10 Correct 69 ms 196304 KB Output is correct
11 Correct 69 ms 196308 KB Output is correct
12 Correct 70 ms 196412 KB Output is correct
13 Correct 71 ms 196360 KB Output is correct
14 Correct 91 ms 196304 KB Output is correct
15 Correct 72 ms 196428 KB Output is correct
16 Incorrect 73 ms 196392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196420 KB Output is correct
2 Correct 72 ms 196356 KB Output is correct
3 Correct 76 ms 196336 KB Output is correct
4 Correct 74 ms 196380 KB Output is correct
5 Correct 71 ms 196428 KB Output is correct
6 Correct 75 ms 196340 KB Output is correct
7 Correct 70 ms 196404 KB Output is correct
8 Correct 83 ms 196420 KB Output is correct
9 Correct 79 ms 196404 KB Output is correct
10 Correct 69 ms 196304 KB Output is correct
11 Correct 69 ms 196308 KB Output is correct
12 Correct 70 ms 196412 KB Output is correct
13 Correct 71 ms 196360 KB Output is correct
14 Correct 91 ms 196304 KB Output is correct
15 Correct 72 ms 196428 KB Output is correct
16 Incorrect 73 ms 196392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196420 KB Output is correct
2 Correct 72 ms 196356 KB Output is correct
3 Correct 76 ms 196336 KB Output is correct
4 Correct 74 ms 196380 KB Output is correct
5 Correct 71 ms 196428 KB Output is correct
6 Correct 75 ms 196340 KB Output is correct
7 Correct 70 ms 196404 KB Output is correct
8 Correct 83 ms 196420 KB Output is correct
9 Correct 79 ms 196404 KB Output is correct
10 Correct 69 ms 196304 KB Output is correct
11 Correct 69 ms 196308 KB Output is correct
12 Correct 70 ms 196412 KB Output is correct
13 Correct 71 ms 196360 KB Output is correct
14 Correct 91 ms 196304 KB Output is correct
15 Correct 72 ms 196428 KB Output is correct
16 Incorrect 73 ms 196392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196420 KB Output is correct
2 Correct 72 ms 196356 KB Output is correct
3 Correct 76 ms 196336 KB Output is correct
4 Correct 74 ms 196380 KB Output is correct
5 Correct 71 ms 196428 KB Output is correct
6 Correct 75 ms 196340 KB Output is correct
7 Correct 70 ms 196404 KB Output is correct
8 Correct 83 ms 196420 KB Output is correct
9 Correct 79 ms 196404 KB Output is correct
10 Correct 69 ms 196304 KB Output is correct
11 Correct 69 ms 196308 KB Output is correct
12 Correct 70 ms 196412 KB Output is correct
13 Correct 71 ms 196360 KB Output is correct
14 Correct 91 ms 196304 KB Output is correct
15 Correct 72 ms 196428 KB Output is correct
16 Incorrect 73 ms 196392 KB Output isn't correct
17 Halted 0 ms 0 KB -