oj.uz

Submission #99017

# Submission time Handle Problem Language Result Execution time Memory
99017 2019-02-28T05:33:56 Z ainta Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 408 ms 378768 KB 
/*#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, Num[200], C[3], V[410][3];
vector<int>U[3];
char p[410];
int D[410][410][410][3];
int main() {
	int i, j, k;
	Num['R'] = 0;
	Num['G'] = 1;
	Num['Y'] = 2;
	scanf("%d", &n);
	scanf("%s", p + 1);
	for (i = 1; i <= n; i++) {
		U[Num[p[i]]].push_back(i);
		V[i][0] = U[0].size();
		V[i][1] = U[1].size();
		V[i][2] = U[2].size();
	}
	for (i = 0; i < 3; i++)C[i] = U[i].size();
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= i; j++) {
			for (k = 0; j+k <= i; k++) {
				D[i][j][k][0]=D[i][j][k][1]=D[i][j][k][2] = 1e9;
			}
		}
	}
	D[1][1][0][0] = (Num[p[1]] != 0);
	D[1][0][1][1] = (Num[p[1]] != 1);
	D[1][0][0][2] = (Num[p[1]] != 2);
	for (i = 1; i < n; i++) {
		for (j = 0; j <= i; j++) {
			for (k = 0; j+k <= i; k++) {
				int l = i - j - k;
				if (j > C[0] || k > C[1] || l > C[2])continue;
				for (int ii = 0; ii < 3; ii++) {
					int t = D[i][j][k][ii];
					if (t > 1e8)continue;
					if (ii!=0 && j != C[0]) {
						int tp = U[0][j];
						int s = max(V[tp][1] - k, 0) + max(V[tp][2] - l, 0);
						D[i + 1][j + 1][k][0] = min(D[i + 1][j + 1][k][0], t + s);
					}
					if (ii!=1 && k != C[1]) {
						int tp = U[1][k];
						int s = max(V[tp][0] - j, 0) + max(V[tp][2] - l, 0);
						D[i + 1][j][k + 1][1] = min(D[i + 1][j][k + 1][1], t + s);
					}
					if (ii!=2 && l != C[2]) {
						int tp = U[2][l];
						int s = max(V[tp][0] - j, 0) + max(V[tp][1] - k, 0);
						D[i + 1][j][k][2] = min(D[i + 1][j][k][2], t + s);
					}
				}
			}
		}
	}
	int res = 1e9;
	for (i = 0; i < 3; i++) {
		res = min(res, D[n][C[0]][C[1]][i]);
	}
	if (res > 1e8) {
		puts("-1");
	}
	else {
		printf("%d\n", res);
	}
}*/

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, Num[200], C[3];
vector<int>U[3];
char p[410];
int D[410][410][410][3];
int main() {
	int i, j, k;
	Num['R'] = 0;
	Num['G'] = 1;
	Num['Y'] = 2;
	scanf("%d", &n);
	scanf("%s", p + 1);
	for (i = 1; i <= n; i++) {
		U[Num[p[i]]].push_back(i);
	}
	for (i = 0; i < 3; i++)C[i] = U[i].size();
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= i; j++) {
			for (k = 0; j + k <= i; k++) {
				D[i][j][k][0] = D[i][j][k][1] = D[i][j][k][2] = 1e9;
			}
		}
	}
	if(C[0])D[1][1][0][0] = abs(1 - U[0][0]);
	if(C[1])D[1][0][1][1] = abs(1 - U[1][0]);
	if(C[2])D[1][0][0][2] = abs(1 - U[2][0]);
	for (i = 1; i < n; i++) {
		for (j = 0; j <= i; j++) {
			for (k = 0; j + k <= i; k++) {
				int l = i - j - k;
				if (j > C[0] || k > C[1] || l > C[2])continue;
				for (int ii = 0; ii < 3; ii++) {
					int t = D[i][j][k][ii];
					if (t > 1e8)continue;
					if (ii != 0 && j != C[0]) {
						D[i + 1][j + 1][k][0] = min(D[i + 1][j + 1][k][0], t + abs(U[0][j] - (i + 1)));
					}
					if (ii != 1 && k != C[1]) {
						D[i + 1][j][k + 1][1] = min(D[i + 1][j][k + 1][1], t + abs(U[1][k] - (i + 1)));
					}
					if (ii != 2 && l != C[2]) {
						D[i + 1][j][k][2] = min(D[i + 1][j][k][2], t + abs(U[2][l] - (i + 1)));
					}
				}
			}
		}
	}
	int res = 1e9;
	for (i = 0; i < 3; i++) {
		res = min(res, D[n][C[0]][C[1]][i]);
	}
	if (res > 1e8) {
		puts("-1");
	}
	else {
		printf("%d\n", res / 2);
	}
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:88:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   U[Num[p[i]]].push_back(i);
             ^
joi2019_ho_t3.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", p + 1);
  ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 1 ms 868 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Incorrect 3 ms 896 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 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 1 ms 868 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Incorrect 3 ms 896 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 408 ms 378664 KB Output is correct
3 Correct 325 ms 376772 KB Output is correct
4 Correct 290 ms 378628 KB Output is correct
5 Correct 331 ms 378708 KB Output is correct
6 Correct 366 ms 378620 KB Output is correct
7 Correct 335 ms 376692 KB Output is correct
8 Correct 322 ms 376740 KB Output is correct
9 Correct 317 ms 374788 KB Output is correct
10 Correct 316 ms 378704 KB Output is correct
11 Correct 316 ms 378712 KB Output is correct
12 Correct 90 ms 99368 KB Output is correct
13 Correct 169 ms 176744 KB Output is correct
14 Correct 225 ms 256984 KB Output is correct
15 Correct 319 ms 378768 KB Output is correct
16 Correct 317 ms 378708 KB Output is correct

Subtask #4
0 / 25.0

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