oj.uz

Submission #287786

# Submission time Handle Problem Language Result Execution time Memory
287786 2020-09-01T00:24:44 Z reymontada61 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 1040344 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;

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 Execution timed out 631 ms 1040248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 631 ms 1040248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 623 ms 1040344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 631 ms 1040248 KB Time limit exceeded
2 Halted 0 ms 0 KB -