oj.uz

Submission #101711

# Submission time Handle Problem Language Result Execution time Memory
101711 2019-03-19T14:39:05 Z KCSC Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 780532 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 405;

int dp[DIM][DIM][DIM][3], idx[3];
int tot[3], psm[DIM][3], lst[DIM][3];

inline int f(int &x, int y) {
	x = min(x, y); }

int main(void) {
#ifdef HOME
	freopen("vegetables.in", "r", stdin);
	freopen("vegetables.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		char ch; cin >> ch;
		if (ch == 'R') { lst[++tot[0]][0] = i; ++psm[i][0]; }
		if (ch == 'G') { lst[++tot[1]][1] = i; ++psm[i][1]; }
		if (ch == 'Y') { lst[++tot[2]][2] = i; ++psm[i][2]; }
		for (int l = 0; l <= 2; ++l) {
			psm[i][l] += psm[i - 1][l]; } }
	memset(dp, 0x3f, sizeof dp);
	for (int l = 0; l <= 2; ++l) {
		dp[0][0][0][l] = 0; }
	for (idx[0] = 0; idx[0] <= tot[0]; ++idx[0]) {
	for (idx[1] = 0; idx[1] <= tot[1]; ++idx[1]) {
	for (idx[2] = 0; idx[2] <= tot[2]; ++idx[2]) {
		for (int ls = 0; ls <= 2; ++ls) {
		for (int cr = 0; cr <= 2; ++cr) {
			if (ls != cr and idx[cr] < tot[cr]) {
				int cst = 0;
				for (int p = 0; p <= 2; ++p) { if (p != cr) {
					cst += max(0, psm[lst[idx[cr] + 1][cr]][p] - idx[p]); } }
				f(dp[idx[0] + (cr == 0)][idx[1] + (cr == 1)][idx[2] + (cr == 2)][cr], dp[idx[0]][idx[1]][idx[2]][ls] + cst); } } } } } }
	
	int v = min( { dp[tot[0]][tot[1]][tot[2]][0], dp[tot[0]][tot[1]][tot[2]][1], dp[tot[0]][tot[1]][tot[2]][2] } );
	cout << (v >= DIM * DIM ? -1 : v) << endl;
	return 0; }

Compilation message

joi2019_ho_t3.cpp: In function 'int f(int&, int)':
joi2019_ho_t3.cpp:10:17: warning: no return statement in function returning non-void [-Wreturn-type]
  x = min(x, y); }
                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 649 ms 780532 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 649 ms 780532 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 636 ms 780260 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 649 ms 780532 KB Time limit exceeded
2 Halted 0 ms 0 KB -