oj.uz

Submission #287789

# Submission time Handle Problem Language Result Execution time Memory
287789 2020-09-01T00:41:28 Z reymontada61 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 9 ms 9088 KB 
#include <bits/stdc++.h>
using namespace std;
 
int n;
string s;
int r, g, b;
const int MXN = 65;
int dp[MXN][MXN][MXN][4];
 
vector<int> rs, gs, bs;
 
int best(int ind, int r, int g, int b, int whi) {
	if (ind == -1) return 0;
	if (dp[ind][r][g][whi] != -1) return dp[ind][r][g][whi];
	int bt = INT_MAX / 2;
	if (r > 0 && whi != 1) {
		bt = min(bt, best(ind-1, r-1, g, b, 1) + abs(rs[r-1] - ind));
	}
	if (g > 0 && whi != 2) {
		bt = min(bt, best(ind-1, r, g-1, b, 2) + abs(gs[g-1] - ind));
	}
	if (b > 0 && whi != 3) {
		bt = min(bt, best(ind-1, r, g, b-1, 3) + abs(bs[b-1] - ind));
	}
	return dp[ind][r][g][whi] = bt;
}
 
signed main() {
 
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXN; j++) {
			for (int l=0; l<MXN; l++) {
				for (int k=0; k<4; k++) {
					dp[i][j][l][k] = -1;
				}
			}
		}
	}
 
	cin >> n >> s;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'R') {
			rs.push_back(i);
			r++;
		}
		if (s[i] == 'G') {
			gs.push_back(i);
			g++;
		}
		if (s[i] == 'Y') {
			bs.push_back(i);
			b++;
		}
	}
	
	int re = best(n-1, r, g, b, 0);
	
	if (re > n * n) {
		cout << -1 << endl;
	}
	else {
		cout << re / 2 << endl;
	}
 
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4584 KB Output is correct
2 Runtime error 9 ms 9088 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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