oj.uz

Submission #220751

# Submission time Handle Problem Language Result Execution time Memory
220751 2020-04-08T16:19:21 Z hanagasumi Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 7 ms 944 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll

using namespace std;
typedef long long ll;

int inf = 1e9 + 100;

signed main() {
	 #ifdef PC 
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 0; i < len(s); i++) {
		if(s[i] == 'R') 
			s[i] = 'a';
		if(s[i] == 'G') 
			s[i] = 'b';
		if(s[i] == 'Y')
			s[i] = 'c';
	}
	vector<int> a, b, c;
	for (int i = 0; i < len(s); i++) {
		if(s[i] == 'a') 
			a.pb(i);
		if(s[i] == 'b') 
			b.pb(i);
		if(s[i] == 'c') 
			c.pb(i);
	}
	int maxa = len(a), maxb = len(b), maxc = len(c);
	// cout << maxa << " " << maxb << " " << maxc << endl;
	int dp[maxa + 1][maxb + 1][maxc + 1][3];
	for (int i = 0; i <= maxa; i++) {
		for (int j = 0; j <= maxb; j++) {
			for (int z = 0; z <= maxc; z++) {
				for (int pr = 0; pr < 3; pr++)
					dp[i][j][z][pr] = inf;
			}
		}
	}
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int i = 0; i <= maxa; i++) {
		for (int j = 0; j <= maxb; j++) {
			for (int z = 0; z <= maxc; z++) {
				for (int pr = 0; pr < 3; pr++) {
					// cout << i << " " << j << " " << z << " " << pr << " " << dp[i][j][z][pr] << endl;
					int pos = i + j + z;
					for (char nxt = 'a'; nxt <= 'c'; nxt++) {
						if(nxt - 'a' == pr) 
							continue;
						if(nxt == 'a' && i == maxa) 
							continue;
						if(nxt == 'b' && j == maxb) 
							continue;
						if(nxt == 'c' && z == maxc) 
							continue;
						if(nxt == 'a') {
							dp[i + 1][j][z][0] = min(dp[i + 1][j][z][0], dp[i][j][z][pr] + max(0, pos - a[i]));
						}
						if(nxt == 'b') {
							dp[i][j + 1][z][1] = min(dp[i][j + 1][z][1], dp[i][j][z][pr] + max(0, pos - b[j]));
						}
						if(nxt == 'c') {
							dp[i][j][z + 1][2] = min(dp[i][j][z + 1][2], dp[i][j][z][pr] + max(0, pos - c[z]));
						}
					}
				}
			}
		}
	}
	int ans = min(dp[maxa][maxb][maxc][0], min(dp[maxa][maxb][maxc][1], dp[maxa][maxb][maxc][2]));
	if(ans == inf) 
		ans = -1;
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 304 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Incorrect 4 ms 384 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 5 ms 384 KB Output is correct
2 Correct 6 ms 944 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 6 ms 768 KB Output is correct
8 Correct 6 ms 768 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 6 ms 896 KB Output is correct
16 Correct 6 ms 768 KB Output is correct

Subtask #4
0 / 25.0

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