oj.uz

Submission #577097

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

const int N = 5005;
const int inf = 1e9;
int dp[2][N][N], a[N];
int l[N], r[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, 100, sizeof dp);
	dp[0][0][0] = 0;
	int res = 0;
	for(int i=0;i<=n;i++){
		for(int x=0;x<=n;x++){
			dp[0][i+1][x] = min(dp[0][i+1][x], dp[0][i][x] + 1);
			if(a[i+1] == -1) dp[0][i+1][x] = min(dp[0][i+1][x], dp[1][i][x] + 1);
			dp[1][i+1][x] = min(dp[1][i+1][x], dp[1][i][x] + 1);
			for(int z=1, is=1;is && z <= a[i];z++){ is = 0;
				if(dp[0][i][x] + (z - 1) * 2 * min(l[i], r[i])<=2*i){
					is = 1;
					dp[0][i + 1][x + z] = min(dp[0][i + 1][x + z], dp[0][i][x] + min(z * 2 * l[i] + 1, z * 2 * r[i] - 1));
					dp[1][i + 1][x + z] = min(dp[1][i + 1][x + 1], dp[0][i][x] + (z - 1) * 2 * min(l[i], r[i]) + 1);
				}
			}
			if(dp[0][i][x] < inf || dp[1][i][x] < inf) res = max(res, x);
		}
	}
	
	ll tot = 0;
	for(int i=0;i<n;i++){
		if(~a[i]) tot += a[i];
	}
	
	//~ cout<<tot<<" "<<res<<"\n";
	cout<<tot - res<<"\n";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 73 ms 196364 KB Output is correct
3 Correct 69 ms 196300 KB Output is correct
4 Correct 72 ms 196300 KB Output is correct
5 Correct 69 ms 196396 KB Output is correct
6 Correct 71 ms 196296 KB Output is correct
7 Correct 79 ms 196280 KB Output is correct
8 Correct 71 ms 196304 KB Output is correct
9 Correct 70 ms 196300 KB Output is correct
10 Correct 70 ms 196300 KB Output is correct
11 Correct 70 ms 196372 KB Output is correct
12 Correct 71 ms 196272 KB Output is correct
13 Correct 68 ms 196372 KB Output is correct
14 Correct 69 ms 196468 KB Output is correct
15 Correct 71 ms 196464 KB Output is correct
16 Incorrect 74 ms 196304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 73 ms 196364 KB Output is correct
3 Correct 69 ms 196300 KB Output is correct
4 Correct 72 ms 196300 KB Output is correct
5 Correct 69 ms 196396 KB Output is correct
6 Correct 71 ms 196296 KB Output is correct
7 Correct 79 ms 196280 KB Output is correct
8 Correct 71 ms 196304 KB Output is correct
9 Correct 70 ms 196300 KB Output is correct
10 Correct 70 ms 196300 KB Output is correct
11 Correct 70 ms 196372 KB Output is correct
12 Correct 71 ms 196272 KB Output is correct
13 Correct 68 ms 196372 KB Output is correct
14 Correct 69 ms 196468 KB Output is correct
15 Correct 71 ms 196464 KB Output is correct
16 Incorrect 74 ms 196304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 73 ms 196364 KB Output is correct
3 Correct 69 ms 196300 KB Output is correct
4 Correct 72 ms 196300 KB Output is correct
5 Correct 69 ms 196396 KB Output is correct
6 Correct 71 ms 196296 KB Output is correct
7 Correct 79 ms 196280 KB Output is correct
8 Correct 71 ms 196304 KB Output is correct
9 Correct 70 ms 196300 KB Output is correct
10 Correct 70 ms 196300 KB Output is correct
11 Correct 70 ms 196372 KB Output is correct
12 Correct 71 ms 196272 KB Output is correct
13 Correct 68 ms 196372 KB Output is correct
14 Correct 69 ms 196468 KB Output is correct
15 Correct 71 ms 196464 KB Output is correct
16 Incorrect 74 ms 196304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 73 ms 196364 KB Output is correct
3 Correct 69 ms 196300 KB Output is correct
4 Correct 72 ms 196300 KB Output is correct
5 Correct 69 ms 196396 KB Output is correct
6 Correct 71 ms 196296 KB Output is correct
7 Correct 79 ms 196280 KB Output is correct
8 Correct 71 ms 196304 KB Output is correct
9 Correct 70 ms 196300 KB Output is correct
10 Correct 70 ms 196300 KB Output is correct
11 Correct 70 ms 196372 KB Output is correct
12 Correct 71 ms 196272 KB Output is correct
13 Correct 68 ms 196372 KB Output is correct
14 Correct 69 ms 196468 KB Output is correct
15 Correct 71 ms 196464 KB Output is correct
16 Incorrect 74 ms 196304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196300 KB Output is correct
2 Correct 73 ms 196364 KB Output is correct
3 Correct 69 ms 196300 KB Output is correct
4 Correct 72 ms 196300 KB Output is correct
5 Correct 69 ms 196396 KB Output is correct
6 Correct 71 ms 196296 KB Output is correct
7 Correct 79 ms 196280 KB Output is correct
8 Correct 71 ms 196304 KB Output is correct
9 Correct 70 ms 196300 KB Output is correct
10 Correct 70 ms 196300 KB Output is correct
11 Correct 70 ms 196372 KB Output is correct
12 Correct 71 ms 196272 KB Output is correct
13 Correct 68 ms 196372 KB Output is correct
14 Correct 69 ms 196468 KB Output is correct
15 Correct 71 ms 196464 KB Output is correct
16 Incorrect 74 ms 196304 KB Output isn't correct
17 Halted 0 ms 0 KB -