oj.uz

Submission #121211

# Submission time Handle Problem Language Result Execution time Memory
121211 2019-06-26T08:08:36 Z 윤교준(#2970) Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 780424 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 405;

int DP[MAXN][MAXN][MAXN][3];

vector<int> AV[3];
int AC[MAXN][3];
int A[MAXN];

int N, Ans = INF;

int f(int a, int b, int c, int v) {
	if(!v) v = AV[0][a];
	else if(1 == v) v = AV[1][b];
	else v = AV[2][c];
	return max(0, AC[v-1][0]-a) + max(0, AC[v-1][1]-b) + max(0, AC[v-1][2]-c);
}

int main() {
	{
		char str[MAXN];
		scanf("%d %s", &N, str+1);
		for(int i = 1; i <= N; i++) {
			if('R' == str[i]) A[i] = 1;
			if('G' == str[i]) A[i] = 2;
		}
	}
	for(int i = 1; i <= N; i++) AV[A[i]].eb(i);
	for(int i = 1; i <= N; i++) {
		for(int t = 0; t < 3; t++) {
			AC[i][t] = AC[i-1][t];
		}
		AC[i][A[i]]++;
	}

	fill(DP[0][0][0], DP[MAXN-1][MAXN-1][MAXN-1]+3, INF);

	if(!AV[0].empty()) DP[1][0][0][0] = AV[0][0] - 1;
	if(!AV[1].empty()) DP[0][1][0][1] = AV[1][0] - 1;
	if(!AV[2].empty()) DP[0][0][1][2] = AV[2][0] - 1;

	for(int l = 1; l < N; l++) {
		for(int a = 0; a <= l && a <= sz(AV[0]); a++) {
			for(int b = 0; b <= l && b <= sz(AV[1]); b++) {
				int c = l-a-b;
				if(c < 0 || sz(AV[2]) < c) continue;
				for(int t = 0; t < 3; t++) {
					int ret = DP[a][b][c][t];
					if(INF <= ret) continue;

					for(int v = 0; v < 3; v++) {
						if(t == v) continue;
						if(!v) {
							if(a == sz(AV[0])) continue;
							upmin(DP[a+1][b][c][0], ret + f(a, b, c, 0));
						} else if(1 == v) {
							if(b == sz(AV[1])) continue;
							upmin(DP[a][b+1][c][1], ret + f(a, b, c, 1));
						} else {
							if(c == sz(AV[2])) continue;
							upmin(DP[a][b][c+1][2], ret + f(a, b, c, 2));
						}
					}
				}
			}
		}
	}

	for(int i = 0; i < 3; i++)
		upmin(Ans, DP[sz(AV[0])][sz(AV[1])][sz(AV[2])][i]);
	
	cout << (INF <= Ans ? -1 : Ans) << endl;
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %s", &N, str+1);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 704 ms 780424 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 704 ms 780424 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 603 ms 780328 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 704 ms 780424 KB Time limit exceeded
2 Halted 0 ms 0 KB -