oj.uz

Submission #287792

# Submission time Handle Problem Language Result Execution time Memory
287792 2020-09-01T01:01:15 Z reymontada61 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 286 ms 511480 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
string s;
int r, g, b;
const int MXN = 405;
int dp[MXN][MXN][MXN][4];

vector<int> rs, gs, bs;

signed main() {


	cin >> n >> s;
	
	int rc = 0, bc = 0, gc = 0;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'R') {
			rs.push_back(i+1);
			r++;
			rc++;
		}
		if (s[i] == 'G') {
			gs.push_back(i+1);
			g++;
			gc++;
		}
		if (s[i] == 'Y') {
			bs.push_back(i+1);
			b++;
			bc++;
		}
	}
	
	s = ' ' + s;
	
	for (int ind=1; ind<=n; ind++) {
		for (int r=0; r<=rc; r++) {
			for (int g=0; g<=gc; g++) {
				int b = ind - r - g;
				if (b > bc || b < 0) {
					for (int whi=0; whi<=3; whi++) {
						dp[ind][r][g][whi] = INT_MAX / 2;
					}
				}
				else {
					for (int whi=0; whi<=3; whi++) {
						///
						
						int bt = INT_MAX / 2;
						if (r > 0 && whi != 1) {
							bt = min(bt, (dp[ind-1][r-1][g][1] + abs(rs[r-1] - ind)));
						}
						if (g > 0 && whi != 2) {
							bt = min(bt, (dp[ind-1][r][g-1][2] + abs(gs[g-1] - ind)));
						}
						if (b > 0 && whi != 3) {
							bt = min(bt, (dp[ind-1][r][g][3] + abs(bs[b-1] - ind)));
						}
						dp[ind][r][g][whi] = bt;
						
						///
					}
				}
			}
		}
	}
	
	int re = dp[n][r][g][0];
	
	if (re > n * n * 2) {
		cout << -1 << endl;
	}
	else {
		cout << re / 2 << endl;
	}

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 800 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct
11 Incorrect 1 ms 768 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 800 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct
11 Incorrect 1 ms 768 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 384 KB Output is correct
2 Correct 285 ms 511480 KB Output is correct
3 Correct 286 ms 510380 KB Output is correct
4 Correct 284 ms 511480 KB Output is correct
5 Correct 283 ms 511352 KB Output is correct
6 Correct 286 ms 511376 KB Output is correct
7 Correct 281 ms 507644 KB Output is correct
8 Correct 285 ms 507640 KB Output is correct
9 Correct 284 ms 506360 KB Output is correct
10 Correct 286 ms 511356 KB Output is correct
11 Correct 283 ms 511480 KB Output is correct
12 Correct 66 ms 121464 KB Output is correct
13 Correct 129 ms 233852 KB Output is correct
14 Correct 197 ms 348664 KB Output is correct
15 Correct 284 ms 508920 KB Output is correct
16 Correct 286 ms 508920 KB Output is correct

Subtask #4
0 / 25.0

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