oj.uz

Submission #1104897

# Submission time Handle Problem Language Result Execution time Memory
1104897 2024-10-24T16:11:54 Z Champ_Naman Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 107 ms 447916 KB 
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'

int dp[401][401][401][3];

inline void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	s = " "+s;

	int p[3][n+1], c[3];
	for(int l=0; l<3; l++){
		p[l][0] = 0;
		c[l] = 0;
	}

	for(int i=1; i<=n; i++){
		if(s[i] == 'R') p[0][++c[0]] = i;
		else if(s[i] == 'G') p[1][++c[1]] = i;
		else p[2][++c[2]] = i;
	}

	for(int l=0; l<3; l++) dp[0][0][0][l] = 0;

	for(int i=1; i<=n; i++){
		for(int r=0; r<=min(c[0], i); r++){
			for(int g=0; g<=min(c[1], i-r); g++){
				int y = i - r - g;
				if(y > c[2]) continue;

				if(r > 0) dp[i][r][g][0] = min(dp[i-1][r-1][g][1], dp[i-1][r-1][g][2]) + max(0, p[0][r] - i);
				else dp[i][r][g][0] = 1e9;

				if(g > 0) dp[i][r][g][1] = min(dp[i-1][r][g-1][0], dp[i-1][r][g-1][2]) + max(0, p[1][g] - i);
				else dp[i][r][g][1] = 1e9;

				if(y > 0) dp[i][r][g][2] = min(dp[i-1][r][g][0], dp[i-1][r][g][1]) + max(0, p[2][y] - i);
				else dp[i][r][g][2] = 1e9;
			}
		}
	}

	int ans = min({dp[n][c[0]][c[1]][0], dp[n][c[0]][c[1]][1], dp[n][c[0]][c[1]][2]});
	cout<<(ans >= 1e9 ? -1 : ans)<<nl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	//cin>>t;
	while(t--) solve();

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 20816 KB Output is correct
5 Correct 3 ms 29008 KB Output is correct
6 Correct 3 ms 29008 KB Output is correct
7 Correct 3 ms 29008 KB Output is correct
8 Correct 3 ms 29188 KB Output is correct
9 Correct 3 ms 29008 KB Output is correct
10 Correct 3 ms 29008 KB Output is correct
11 Incorrect 4 ms 29008 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 20816 KB Output is correct
5 Correct 3 ms 29008 KB Output is correct
6 Correct 3 ms 29008 KB Output is correct
7 Correct 3 ms 29008 KB Output is correct
8 Correct 3 ms 29188 KB Output is correct
9 Correct 3 ms 29008 KB Output is correct
10 Correct 3 ms 29008 KB Output is correct
11 Incorrect 4 ms 29008 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 96 ms 422108 KB Output is correct
3 Correct 102 ms 417608 KB Output is correct
4 Correct 101 ms 425640 KB Output is correct
5 Correct 96 ms 419912 KB Output is correct
6 Correct 97 ms 426328 KB Output is correct
7 Correct 107 ms 422988 KB Output is correct
8 Correct 89 ms 441068 KB Output is correct
9 Correct 89 ms 441680 KB Output is correct
10 Correct 89 ms 442440 KB Output is correct
11 Correct 89 ms 441676 KB Output is correct
12 Correct 33 ms 369928 KB Output is correct
13 Correct 42 ms 360776 KB Output is correct
14 Correct 58 ms 400968 KB Output is correct
15 Correct 103 ms 447916 KB Output is correct
16 Correct 97 ms 445520 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 20816 KB Output is correct
5 Correct 3 ms 29008 KB Output is correct
6 Correct 3 ms 29008 KB Output is correct
7 Correct 3 ms 29008 KB Output is correct
8 Correct 3 ms 29188 KB Output is correct
9 Correct 3 ms 29008 KB Output is correct
10 Correct 3 ms 29008 KB Output is correct
11 Incorrect 4 ms 29008 KB Output isn't correct
12 Halted 0 ms 0 KB -