oj.uz

Submission #1104870

# Submission time Handle Problem Language Result Execution time Memory
1104870 2024-10-24T15:16:08 Z Champ_Naman Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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++) for(int i=1; i<=n; i++) p[l][i] = -1;
	p[0][0] = p[1][0] = p[2][0] = c[0] = c[1] = c[2] = 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 r=0; r<=n; r++) for(int g=0; g<=n; g++) for(int l=0; l<3; l++) dp[0][r][g][l] = 1e18;
	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<=n; r++){
			for(int g=0; g<=n; g++){
				int y = i - r - g;

				for(int l=0; l<3; l++){
					if(y < 0 or (l == 0 ? r : (l == 1 ? g : y)) == 0){
						dp[i][r][g][l] = 1e18;
						continue;
					}

					dp[i][r][g][l] = 1e18;
					if(l == 0 and p[0][r] != -1) dp[i][r][g][l] = min(dp[i-1][r-1][g][1], dp[i-1][r-1][g][2]) + max(0LL, p[0][r] - i);
					if(l == 1 and p[1][g] != -1) dp[i][r][g][l] = min(dp[i-1][r][g-1][0], dp[i-1][r][g-1][2]) + max(0LL, p[1][g] - i);
					if(l == 2 and p[2][y] != -1) dp[i][r][g][l] = min(dp[i-1][r][g][0], dp[i-1][r][g][1]) + max(0LL, p[2][y] - i);
				}
			}
		}
	}

	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 >= 1e18 ? -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 2 ms 6480 KB Output is correct
4 Correct 3 ms 22864 KB Output is correct
5 Correct 4 ms 35408 KB Output is correct
6 Correct 5 ms 35408 KB Output is correct
7 Correct 4 ms 35408 KB Output is correct
8 Correct 4 ms 35408 KB Output is correct
9 Correct 3 ms 35408 KB Output is correct
10 Correct 4 ms 35660 KB Output is correct
11 Incorrect 4 ms 35352 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 2 ms 6480 KB Output is correct
4 Correct 3 ms 22864 KB Output is correct
5 Correct 4 ms 35408 KB Output is correct
6 Correct 5 ms 35408 KB Output is correct
7 Correct 4 ms 35408 KB Output is correct
8 Correct 4 ms 35408 KB Output is correct
9 Correct 3 ms 35408 KB Output is correct
10 Correct 4 ms 35660 KB Output is correct
11 Incorrect 4 ms 35352 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Execution timed out 747 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

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 2 ms 6480 KB Output is correct
4 Correct 3 ms 22864 KB Output is correct
5 Correct 4 ms 35408 KB Output is correct
6 Correct 5 ms 35408 KB Output is correct
7 Correct 4 ms 35408 KB Output is correct
8 Correct 4 ms 35408 KB Output is correct
9 Correct 3 ms 35408 KB Output is correct
10 Correct 4 ms 35660 KB Output is correct
11 Incorrect 4 ms 35352 KB Output isn't correct
12 Halted 0 ms 0 KB -