Submission #891830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891830	2023-12-24T07:24:42 Z	Vvnx	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	51 ms	302420 KB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 403;
const ll INF = 1e9;

ll n,r,g,b;
string s;
vector<ll> pos[5];
ll dp[N][N][N][3];

int main() {
	cin >> n >> s;
	s = '!' + s;
	for(int i=1; i<=n; i++) {
		if(s[i] == 'R') {
			r++;
			pos[0].pb(i);
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(i);
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(i);
		}
	}
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				for(int l=0; l<=2; l++) dp[i][j][k][l] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1],dp[i-1][j][k][2]) + abs(i+j+k-pos[0][i-1]);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + abs(i+j+k-pos[1][j-1]);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + abs(i+j+k-pos[2][k-1]);
			}
		}
	}
	ll ans = min({dp[r][g][b][0],dp[r][g][b][1],dp[r][g][b][2]});
	if(ans >= INF) cout << -1 << endl;
	else cout << ans/2 << endl;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	14680 KB	Output is correct
8	Correct	1 ms	12636 KB	Output is correct
9	Correct	2 ms	12636 KB	Output is correct
10	Correct	3 ms	20828 KB	Output is correct
11	Incorrect	2 ms	10748 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #2

0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	14680 KB	Output is correct
8	Correct	1 ms	12636 KB	Output is correct
9	Correct	2 ms	12636 KB	Output is correct
10	Correct	3 ms	20828 KB	Output is correct
11	Incorrect	2 ms	10748 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	1 ms	4444 KB	Output is correct
2	Correct	46 ms	301104 KB	Output is correct
3	Correct	50 ms	299788 KB	Output is correct
4	Correct	51 ms	300112 KB	Output is correct
5	Correct	48 ms	300108 KB	Output is correct
6	Correct	46 ms	299860 KB	Output is correct
7	Correct	47 ms	301652 KB	Output is correct
8	Correct	46 ms	301600 KB	Output is correct
9	Correct	46 ms	301184 KB	Output is correct
10	Correct	46 ms	302420 KB	Output is correct
11	Correct	47 ms	302360 KB	Output is correct
12	Correct	20 ms	197464 KB	Output is correct
13	Correct	26 ms	247092 KB	Output is correct
14	Correct	36 ms	267348 KB	Output is correct
15	Correct	47 ms	300772 KB	Output is correct
16	Correct	48 ms	299404 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	14680 KB	Output is correct
8	Correct	1 ms	12636 KB	Output is correct
9	Correct	2 ms	12636 KB	Output is correct
10	Correct	3 ms	20828 KB	Output is correct
11	Incorrect	2 ms	10748 KB	Output isn't correct
12	Halted	0 ms	0 KB	-