oj.uz

Submission #107289

# Submission time Handle Problem Language Result Execution time Memory
107289 2019-04-23T05:52:27 Z Diuven Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 401 ms 4344 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 1<<20;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;


/*
앞에서부터, R, G, Y를 몇개씩 썼는지. 마지막이 뭔지
-> D[R][G][Y][c] = (distance with the nearest c) + _min(D[R-(c==0)][G-(c==1)][(c+1)/3], D[R-(c==0)][G-(c==1)][(c+2)/3]);
*/
int n, D[2][410][410][3];
int X[3][410];
char S[410];

inline int f(int x, int y){ return x<y ? y-x : 0; }
inline int _min(int x, int y){ return x<y ? x : y; }

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>(S+1);

	for(int i=1; i<=n; i++) X[0][i] = X[1][i] = X[2][i] = INF;

	for(int i=1; i<=n; i++){
		static int r, g, y;
		if(S[i]=='R') X[0][++r] = i;
		if(S[i]=='G') X[1][++g] = i;
		if(S[i]=='Y') X[2][++y] = i;
	}

	for(int r=0; r<=n; r++) for(int g=0; g<=n; g++) for(int c=0; c<3; c++)
		D[0][r][g][c] = INF;
	D[0][0][0][0] = D[0][0][0][1] = D[0][0][0][2] = 0;

	// for(int r=0; r<=n; r++, cout<<'\n')
	// 	for(int g=0; g<=n; g++, cout<<'\n')
	// 		for(int c=0; c<3; c++)
	// 			cout<<D[0][r][g][c]<<' ';
	// cout<<'\n';

	for(int i=1; i<=n; i++){
		int b = i&1;
		for(int r=0; r<=n; r++)
			for(int g=0; g<=n; g++)
				for(int c=0; c<3; c++)
					D[b][r][g][c] = INF;

		for(int r=0; r<=i; r++)
			for(int g=0; g+r<=i; g++){
				int Y[3] = {r,g,i-r-g};
				for(int c=0; c<3; c++){
					if(Y[c]<1){ D[b][r][g][c] = INF; continue; }
					int dist = f(i, X[c][Y[c]]);
					int p = (c+1)%3, q = (c+2)%3;
					int *E= D[!b][r-(c==0)][g-(c==1)];
					D[b][r][g][c] = dist + _min(E[p], E[q]);
				}
			}

		// for(int r=0; r<=n; r++, cout<<'\n')
		// 	for(int g=0; g<=n; g++, cout<<'\n')
		// 		for(int c=0; c<3; c++)
		// 			cout<<D[b][r][g][c]<<' ';
		// cout<<'\n';
	}

	/*

	for(int r=0; r<=n; r++) for(int g=0; g<=n; g++)
		D[0][r][g] = INF;
	D[0][0][0] = 0;

	for(int i=1; i<=n; i++){
		int b = i&1, c = !b;
		for(int r=0; r<=n; r++) for(int g=0; g<=n; g++) D[b][r][g] = INF;
		for(int r=0; r<=i; r++)
			for(int g=0; r+g<=i; g++){
				D[b][r+1][g] = _min(D[b][r+1][g], D[c][r][g]+f(i,X[0][r+1]));
				D[b][r][g+1] = _min(D[b][r][g+1], D[c][r][g]+f(i,X[1][g+1]));
				D[b][r][g] = _min(D[b][r][g], D[c][r][g]+f(i,X[2][i-r-g]));
			}
		cout<<'\n';
		for(int r=0; r<=n; r++, cout<<'\n') for(int g=0; g<=n; g++) cout<<D[b][r][g]<<' ';
	}
	*/

	int ans = INF;
	for(int r=0; r<=n; r++)
		for(int g=0; r+g<=n; g++)
			for(int c=0; c<3; c++)
				ans = _min(ans, D[n&1][r][g][c]);
	if(ans>=INF) ans = -1;
	cout<<ans<<'\n';

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Incorrect 3 ms 512 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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Incorrect 3 ms 512 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 2 ms 384 KB Output is correct
2 Correct 341 ms 4260 KB Output is correct
3 Correct 401 ms 4344 KB Output is correct
4 Correct 318 ms 4344 KB Output is correct
5 Correct 311 ms 4224 KB Output is correct
6 Correct 281 ms 4224 KB Output is correct
7 Correct 299 ms 4224 KB Output is correct
8 Correct 324 ms 4224 KB Output is correct
9 Correct 347 ms 4344 KB Output is correct
10 Correct 327 ms 4344 KB Output is correct
11 Correct 291 ms 4252 KB Output is correct
12 Correct 43 ms 2304 KB Output is correct
13 Correct 107 ms 2944 KB Output is correct
14 Correct 177 ms 3584 KB Output is correct
15 Correct 328 ms 4224 KB Output is correct
16 Correct 318 ms 4316 KB Output is correct

Subtask #4
0 / 25.0

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