답안 #486777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486777	2021-11-12T18:29:03 Z	socho	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	118 ms	189768 KB

joi2019_ho_t3

/*
	Going for full
*/
#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
#define endl '\n'
// #define double long double
// #define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;
// #define cerr if(0) cerr
#define debug(x) cerr << #x << ": " << x << endl;
 
int n;
string s;
int r, g, b;
const int MXN = 405;
int dp[MXN][MXN][MXN][4];
 
vector<int> rs, gs, bs;
 
int pfr[MXN];
int pfg[MXN];
int pfb[MXN];
 
signed main() {
 
 
	cin >> n >> s;
	
	int rc = 0, bc = 0, gc = 0;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'R') {
			rs.push_back(i+1);
			r++;
			rc++;
		}
		if (s[i] == 'G') {
			gs.push_back(i+1);
			g++;
			gc++;
		}
		if (s[i] == 'Y') {
			bs.push_back(i+1);
			b++;
			bc++;
		}
		pfr[i+1] = r;
		pfg[i+1] = g;
		pfb[i+1] = b;
	}
	
	s = ' ' + s;
	
	for (int ind=1; ind<=n; ind++) {
		for (int r=0; r<=rc; r++) {
			for (int g=0; g<=gc; g++) {
				int b = ind - r - g;
				if (b >= 0 && b <= bc) {
					for (int whi=1; whi<=3; whi++) {
						
						int re = INT_MAX / 2;
						
						if (whi != 1 && r > 0) {
							int h = dp[ind-1][r-1][g][1];
							int l = rs[r-1];
							h += max(l + max(g - pfg[l], 0) + max(b - pfb[l], 0) - ind, 0);
							re = min(re, h);
						}
						
						if (whi != 2 && g > 0) {
							int h = dp[ind-1][r][g-1][2];
							int l = gs[g-1];
							h += max(l + max(b - pfb[l], 0) + max(r - pfr[l], 0) - ind, 0);
							re = min(re, h);
						}
						
						if (whi != 3 && b > 0) {
							int h = dp[ind-1][r][g][3];
							int l = bs[b-1];
							h += max(l + max(g - pfg[l], 0) + max(r - pfr[l], 0) - ind, 0);
							re = min(re, h);
						}
						
						dp[ind][r][g][whi] = re;	
					}
				}
			}
		}
	}
 
	
	int re = dp[n][r][g][1];
	for (int i=1; i<=3; i++) re = min(re, dp[n][r][g][i]);
	
	if (re > n * n * 2) {
		cout << -1 << endl;
	}
	else {
		cout << re << endl;
	}
 
}

Compilation message

joi2019_ho_t3.cpp: In function 'void usaco()':
joi2019_ho_t3.cpp:18:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	464 KB	Output is correct
5	Correct	0 ms	592 KB	Output is correct
6	Correct	0 ms	592 KB	Output is correct
7	Correct	0 ms	592 KB	Output is correct
8	Correct	1 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	1 ms	592 KB	Output is correct
11	Correct	1 ms	592 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	0 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	1 ms	592 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	464 KB	Output is correct
5	Correct	0 ms	592 KB	Output is correct
6	Correct	0 ms	592 KB	Output is correct
7	Correct	0 ms	592 KB	Output is correct
8	Correct	1 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	1 ms	592 KB	Output is correct
11	Correct	1 ms	592 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	0 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	1 ms	592 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	2 ms	4304 KB	Output is correct
19	Correct	2 ms	4048 KB	Output is correct
20	Correct	2 ms	4432 KB	Output is correct
21	Correct	2 ms	4048 KB	Output is correct
22	Correct	2 ms	4304 KB	Output is correct
23	Correct	2 ms	3792 KB	Output is correct
24	Correct	1 ms	2896 KB	Output is correct
25	Correct	2 ms	4176 KB	Output is correct
26	Correct	2 ms	4432 KB	Output is correct
27	Correct	3 ms	4412 KB	Output is correct
28	Correct	3 ms	4176 KB	Output is correct
29	Correct	2 ms	4276 KB	Output is correct
30	Correct	2 ms	3812 KB	Output is correct
31	Correct	2 ms	3640 KB	Output is correct
32	Correct	2 ms	3896 KB	Output is correct
33	Correct	2 ms	4176 KB	Output is correct
34	Correct	2 ms	4048 KB	Output is correct
35	Correct	2 ms	4048 KB	Output is correct
36	Correct	2 ms	4048 KB	Output is correct
37	Correct	2 ms	3152 KB	Output is correct
38	Correct	2 ms	3408 KB	Output is correct
39	Correct	2 ms	4048 KB	Output is correct
40	Correct	1 ms	720 KB	Output is correct
41	Correct	1 ms	2640 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	68 ms	163740 KB	Output is correct
3	Correct	69 ms	162956 KB	Output is correct
4	Correct	69 ms	163784 KB	Output is correct
5	Correct	71 ms	163956 KB	Output is correct
6	Correct	67 ms	163776 KB	Output is correct
7	Correct	67 ms	163016 KB	Output is correct
8	Correct	66 ms	163016 KB	Output is correct
9	Correct	66 ms	162144 KB	Output is correct
10	Correct	68 ms	163788 KB	Output is correct
11	Correct	66 ms	163840 KB	Output is correct
12	Correct	17 ms	44496 KB	Output is correct
13	Correct	32 ms	77656 KB	Output is correct
14	Correct	44 ms	112200 KB	Output is correct
15	Correct	67 ms	163752 KB	Output is correct
16	Correct	69 ms	163780 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	464 KB	Output is correct
5	Correct	0 ms	592 KB	Output is correct
6	Correct	0 ms	592 KB	Output is correct
7	Correct	0 ms	592 KB	Output is correct
8	Correct	1 ms	592 KB	Output is correct
9	Correct	1 ms	592 KB	Output is correct
10	Correct	1 ms	592 KB	Output is correct
11	Correct	1 ms	592 KB	Output is correct
12	Correct	1 ms	592 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	0 ms	592 KB	Output is correct
15	Correct	1 ms	592 KB	Output is correct
16	Correct	1 ms	592 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	2 ms	4304 KB	Output is correct
19	Correct	2 ms	4048 KB	Output is correct
20	Correct	2 ms	4432 KB	Output is correct
21	Correct	2 ms	4048 KB	Output is correct
22	Correct	2 ms	4304 KB	Output is correct
23	Correct	2 ms	3792 KB	Output is correct
24	Correct	1 ms	2896 KB	Output is correct
25	Correct	2 ms	4176 KB	Output is correct
26	Correct	2 ms	4432 KB	Output is correct
27	Correct	3 ms	4412 KB	Output is correct
28	Correct	3 ms	4176 KB	Output is correct
29	Correct	2 ms	4276 KB	Output is correct
30	Correct	2 ms	3812 KB	Output is correct
31	Correct	2 ms	3640 KB	Output is correct
32	Correct	2 ms	3896 KB	Output is correct
33	Correct	2 ms	4176 KB	Output is correct
34	Correct	2 ms	4048 KB	Output is correct
35	Correct	2 ms	4048 KB	Output is correct
36	Correct	2 ms	4048 KB	Output is correct
37	Correct	2 ms	3152 KB	Output is correct
38	Correct	2 ms	3408 KB	Output is correct
39	Correct	2 ms	4048 KB	Output is correct
40	Correct	1 ms	720 KB	Output is correct
41	Correct	1 ms	2640 KB	Output is correct
42	Correct	1 ms	468 KB	Output is correct
43	Correct	68 ms	163740 KB	Output is correct
44	Correct	69 ms	162956 KB	Output is correct
45	Correct	69 ms	163784 KB	Output is correct
46	Correct	71 ms	163956 KB	Output is correct
47	Correct	67 ms	163776 KB	Output is correct
48	Correct	67 ms	163016 KB	Output is correct
49	Correct	66 ms	163016 KB	Output is correct
50	Correct	66 ms	162144 KB	Output is correct
51	Correct	68 ms	163788 KB	Output is correct
52	Correct	66 ms	163840 KB	Output is correct
53	Correct	17 ms	44496 KB	Output is correct
54	Correct	32 ms	77656 KB	Output is correct
55	Correct	44 ms	112200 KB	Output is correct
56	Correct	67 ms	163752 KB	Output is correct
57	Correct	69 ms	163780 KB	Output is correct
58	Correct	109 ms	176980 KB	Output is correct
59	Correct	109 ms	188064 KB	Output is correct
60	Correct	118 ms	186100 KB	Output is correct
61	Correct	105 ms	182532 KB	Output is correct
62	Correct	71 ms	165448 KB	Output is correct
63	Correct	74 ms	168456 KB	Output is correct
64	Correct	89 ms	181016 KB	Output is correct
65	Correct	97 ms	182924 KB	Output is correct
66	Correct	114 ms	182444 KB	Output is correct
67	Correct	99 ms	169292 KB	Output is correct
68	Correct	104 ms	184136 KB	Output is correct
69	Correct	106 ms	184904 KB	Output is correct
70	Correct	104 ms	183992 KB	Output is correct
71	Correct	109 ms	189768 KB	Output is correct
72	Correct	58 ms	130924 KB	Output is correct
73	Correct	7 ms	12240 KB	Output is correct

답안 #486777

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
25.0 / 25.0