Submission #1113590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113590	2024-11-16T19:04:24 Z	Dan4Life	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	418 ms	410624 KB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
 
using vi = vector<int>;
using ll = long long;
using ar2 = array<ll,2>;
 
const int N = (int)4e2+10;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
 
 
vi v[3];
string s;
int n, cnt[3];
int dp[N][3][N/2][N/2];

int num(int cnt0, int cnt1, int cnt2, int f0, int f1, int f2){
	if(!cnt0) return 0;
	int n1 = 0, n2 = 0, XD = v[f0][cnt0-1];
	if(cnt1 and v[f1][cnt1-1] > XD){
		int pos = lower_bound(all(v[f1]),XD)-begin(v[f1]);
		n1 = cnt1-pos;
	}
	if(cnt2 and v[f2][cnt2-1] > XD){
		int pos = lower_bound(all(v[f2]),XD)-begin(v[f2]);
		n2 = cnt2-pos;
	}
	return n1+n2;
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++){
		char u = s[i];
		if(u=='R') s[i]=0;
		else if(u=='G') s[i]=1;
		else s[i]=2;
		cnt[s[i]]++; v[s[i]].pb(i+1);
	}
	if(cnt[0]>max(cnt[1],cnt[2]))
		swap(cnt[0],cnt[2]), swap(v[0],v[2]);
	else if(cnt[1]>max(cnt[0],cnt[2]))
		swap(cnt[1],cnt[2]), swap(v[1],v[2]);
	memset(dp,0x3f3f3f3f,sizeof(dp));
	if(cnt[0]) dp[1][0][1][0] = v[0][0]-1;
	if(cnt[1]) dp[1][1][0][1] = v[1][0]-1;
	if(cnt[2]) dp[1][2][0][0] = v[2][0]-1;
	int ans = INF;
	for(int i = 2; i <= n; i++){
		for(int j = 0; j < 3; j++){
			for(int m = 0; m < 3; m++){
				if(m==j) continue;
				for(int k = 0; k <= min(i,cnt[0]); k++){
					for(int l = 0; l <= min(i,cnt[1]); l++){
						int o = i-k-l; if(o>i or o>cnt[2]) continue;
						if(k and j==0){
							int f0 = v[0][k-1]+num(k,l,o,0,1,2);
							if(f0>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k-1][l]+f0-i);
						}
						if(l and j==1){
							int f1 = v[1][l-1]+num(l,k,o,1,0,2);
							if(f1>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l-1]+f1-i);
						}
						if(o and j==2){
							int f2 = v[2][o-1]+num(o,k,l,2,0,1);
							if(f2>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l]+f2-i);
						}
						
					}
				}
			}
		}
	}
	for(int j = 0; j < 3; j++)
		for(int k = 0; k <= cnt[0]; k++)
			for(int l = 0; l <= cnt[1]; l++)
				ans = min(ans, dp[n][j][k][l]);
	if(ans>=INF) ans=-1;
	cout << ans << "\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:44:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |   cnt[s[i]]++; v[s[i]].pb(i+1);
      |           ^
joi2019_ho_t3.cpp:44:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |   cnt[s[i]]++; v[s[i]].pb(i+1);
      |                      ^

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	202708 KB	Output is correct
2	Correct	143 ms	202572 KB	Output is correct
3	Correct	134 ms	202596 KB	Output is correct
4	Correct	144 ms	202572 KB	Output is correct
5	Correct	142 ms	202572 KB	Output is correct
6	Correct	142 ms	202568 KB	Output is correct
7	Correct	150 ms	202568 KB	Output is correct
8	Correct	131 ms	202572 KB	Output is correct
9	Correct	136 ms	202568 KB	Output is correct
10	Correct	135 ms	202672 KB	Output is correct
11	Correct	135 ms	202540 KB	Output is correct
12	Correct	134 ms	202568 KB	Output is correct
13	Correct	135 ms	202564 KB	Output is correct
14	Correct	141 ms	202644 KB	Output is correct
15	Correct	144 ms	202568 KB	Output is correct
16	Correct	135 ms	202520 KB	Output is correct
17	Correct	146 ms	202568 KB	Output is correct

Subtask #2
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	202708 KB	Output is correct
2	Correct	143 ms	202572 KB	Output is correct
3	Correct	134 ms	202596 KB	Output is correct
4	Correct	144 ms	202572 KB	Output is correct
5	Correct	142 ms	202572 KB	Output is correct
6	Correct	142 ms	202568 KB	Output is correct
7	Correct	150 ms	202568 KB	Output is correct
8	Correct	131 ms	202572 KB	Output is correct
9	Correct	136 ms	202568 KB	Output is correct
10	Correct	135 ms	202672 KB	Output is correct
11	Correct	135 ms	202540 KB	Output is correct
12	Correct	134 ms	202568 KB	Output is correct
13	Correct	135 ms	202564 KB	Output is correct
14	Correct	141 ms	202644 KB	Output is correct
15	Correct	144 ms	202568 KB	Output is correct
16	Correct	135 ms	202520 KB	Output is correct
17	Correct	146 ms	202568 KB	Output is correct
18	Correct	148 ms	202568 KB	Output is correct
19	Correct	133 ms	202568 KB	Output is correct
20	Correct	144 ms	202792 KB	Output is correct
21	Correct	144 ms	202568 KB	Output is correct
22	Correct	152 ms	202692 KB	Output is correct
23	Correct	139 ms	202568 KB	Output is correct
24	Correct	150 ms	202564 KB	Output is correct
25	Correct	144 ms	202576 KB	Output is correct
26	Correct	141 ms	202580 KB	Output is correct
27	Correct	138 ms	202684 KB	Output is correct
28	Correct	136 ms	202568 KB	Output is correct
29	Correct	130 ms	202568 KB	Output is correct
30	Correct	131 ms	202568 KB	Output is correct
31	Correct	133 ms	202568 KB	Output is correct
32	Correct	132 ms	202744 KB	Output is correct
33	Correct	133 ms	202660 KB	Output is correct
34	Correct	133 ms	202660 KB	Output is correct
35	Correct	133 ms	202564 KB	Output is correct
36	Correct	132 ms	202568 KB	Output is correct
37	Correct	132 ms	202528 KB	Output is correct
38	Correct	132 ms	202568 KB	Output is correct
39	Correct	142 ms	202668 KB	Output is correct
40	Correct	142 ms	202576 KB	Output is correct
41	Correct	138 ms	202568 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	202676 KB	Output is correct
2	Runtime error	418 ms	410624 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	202708 KB	Output is correct
2	Correct	143 ms	202572 KB	Output is correct
3	Correct	134 ms	202596 KB	Output is correct
4	Correct	144 ms	202572 KB	Output is correct
5	Correct	142 ms	202572 KB	Output is correct
6	Correct	142 ms	202568 KB	Output is correct
7	Correct	150 ms	202568 KB	Output is correct
8	Correct	131 ms	202572 KB	Output is correct
9	Correct	136 ms	202568 KB	Output is correct
10	Correct	135 ms	202672 KB	Output is correct
11	Correct	135 ms	202540 KB	Output is correct
12	Correct	134 ms	202568 KB	Output is correct
13	Correct	135 ms	202564 KB	Output is correct
14	Correct	141 ms	202644 KB	Output is correct
15	Correct	144 ms	202568 KB	Output is correct
16	Correct	135 ms	202520 KB	Output is correct
17	Correct	146 ms	202568 KB	Output is correct
18	Correct	148 ms	202568 KB	Output is correct
19	Correct	133 ms	202568 KB	Output is correct
20	Correct	144 ms	202792 KB	Output is correct
21	Correct	144 ms	202568 KB	Output is correct
22	Correct	152 ms	202692 KB	Output is correct
23	Correct	139 ms	202568 KB	Output is correct
24	Correct	150 ms	202564 KB	Output is correct
25	Correct	144 ms	202576 KB	Output is correct
26	Correct	141 ms	202580 KB	Output is correct
27	Correct	138 ms	202684 KB	Output is correct
28	Correct	136 ms	202568 KB	Output is correct
29	Correct	130 ms	202568 KB	Output is correct
30	Correct	131 ms	202568 KB	Output is correct
31	Correct	133 ms	202568 KB	Output is correct
32	Correct	132 ms	202744 KB	Output is correct
33	Correct	133 ms	202660 KB	Output is correct
34	Correct	133 ms	202660 KB	Output is correct
35	Correct	133 ms	202564 KB	Output is correct
36	Correct	132 ms	202568 KB	Output is correct
37	Correct	132 ms	202528 KB	Output is correct
38	Correct	132 ms	202568 KB	Output is correct
39	Correct	142 ms	202668 KB	Output is correct
40	Correct	142 ms	202576 KB	Output is correct
41	Correct	138 ms	202568 KB	Output is correct
42	Correct	138 ms	202676 KB	Output is correct
43	Runtime error	418 ms	410624 KB	Execution killed with signal 11
44	Halted	0 ms	0 KB	-

Submission #1113590

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
0 / 15.0

Subtask #4
0 / 25.0