oj.uz

Submission #1101931

# Submission time Handle Problem Language Result Execution time Memory
1101931 2024-10-17T08:04:04 Z hqminhuwu Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 176 ms 8144 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
	bool minz(X &x, const Y &y) {
		if (x > y) {
			x = y;
			return true;
		} return false;
	}
template<class X, class Y>
	bool maxz(X &x, const Y &y) {
		if (x < y) {
			x = y;
			return true;
		} return false;
	}

const int N = 4e2 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

ll n, dp[2][N][N][3], c[3];
string s;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef kaguya
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> s;

	s = '#' + s;
	memset (dp, 63, sizeof dp);
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

	forr (i, 1, n){
		if (s[i] == 'R'){
			c[0]++;
		} else if (s[i] == 'G'){
			c[1]++;
		} else {
			c[2]++;
		}

		forf (j, 0, i){
			forr (k, 0, i - j){
				forr (t, 0, 2){
					forr (w, 0, 2){
						if (w == t) continue;
						int nj = j, nk = k;
						
						if (w == 0){
							nj++;
						} else if (w == 1){
							nk++;
						}

						minz(dp[i & 1][nj][nk][w], dp[(i - 1) & 1][j][k][t]);
					}
				}
			}
		}

		forr (j, 0, i){
			forr (k, 0, i - j){
				forr (t, 0, 2){
					dp[i & 1][j][k][t] += abs(c[0] - j) + abs(c[1] - k) + abs(c[2] - (i - j - k));
				}
			}
		}

		forr (j, 0, i){
			forr (k, 0, i){
				forr (t, 0, 2){
					dp[(i - 1) & 1][j][k][t] = oo;
				}
			}
		}


		// forr (j, 0, i){
		// 	forr (k, 0, i - j){
		// 		cout << dp[i & 1][j][k][0] << " " << dp[i & 1][j][k][1] << " " << dp[i & 1][j][k][2] << " ";
		// 	}
		// 	cout << "\n";
		// }
		// cout << "\n";
	}

	ll res = oo;

	forr (i, 0, 2)
		minz (res, dp[n & 1][c[0]][c[1]][i]);
	

	cout << (res >= oo ? -1 : res / 2) << "\n";

	return 0;
}
/*



*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8016 KB Output is correct
2 Correct 2 ms 8016 KB Output is correct
3 Correct 3 ms 8016 KB Output is correct
4 Correct 3 ms 8016 KB Output is correct
5 Correct 3 ms 8016 KB Output is correct
6 Correct 3 ms 8016 KB Output is correct
7 Correct 3 ms 8016 KB Output is correct
8 Correct 3 ms 8016 KB Output is correct
9 Correct 3 ms 8016 KB Output is correct
10 Correct 3 ms 8016 KB Output is correct
11 Incorrect 2 ms 8016 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 2 ms 8016 KB Output is correct
2 Correct 162 ms 8016 KB Output is correct
3 Correct 159 ms 8016 KB Output is correct
4 Correct 169 ms 8016 KB Output is correct
5 Correct 163 ms 8016 KB Output is correct
6 Correct 160 ms 8144 KB Output is correct
7 Correct 158 ms 8016 KB Output is correct
8 Correct 176 ms 8016 KB Output is correct
9 Correct 156 ms 8016 KB Output is correct
10 Correct 161 ms 8016 KB Output is correct
11 Correct 165 ms 8016 KB Output is correct
12 Correct 25 ms 8016 KB Output is correct
13 Correct 73 ms 8016 KB Output is correct
14 Correct 133 ms 8016 KB Output is correct
15 Correct 162 ms 8016 KB Output is correct
16 Correct 167 ms 8016 KB Output is correct

Subtask #4
0 / 25.0

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