oj.uz

Submission #891829

# Submission time Handle Problem Language Result Execution time Memory
891829 2023-12-24T07:19:58 Z Vvnx Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 54 ms 300628 KB 
#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]);
//				else dp[i][j][k][0] = INF;
				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]);
//				else dp[i][j][k][1] = INF;
				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]);
//				else dp[i][j][k][2] = INF;
			}
		}
	}
	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 0 ms 2392 KB Output is correct
3 Correct 1 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 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 1 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Incorrect 2 ms 10584 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 0 ms 2392 KB Output is correct
3 Correct 1 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 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 1 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Incorrect 2 ms 10584 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 54 ms 288052 KB Output is correct
3 Correct 48 ms 287824 KB Output is correct
4 Correct 47 ms 290384 KB Output is correct
5 Correct 46 ms 290384 KB Output is correct
6 Correct 49 ms 290392 KB Output is correct
7 Correct 47 ms 289620 KB Output is correct
8 Correct 47 ms 289616 KB Output is correct
9 Correct 48 ms 289148 KB Output is correct
10 Correct 48 ms 290316 KB Output is correct
11 Correct 46 ms 298696 KB Output is correct
12 Correct 21 ms 197456 KB Output is correct
13 Correct 26 ms 245636 KB Output is correct
14 Correct 35 ms 265844 KB Output is correct
15 Correct 46 ms 300628 KB Output is correct
16 Correct 47 ms 299592 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 0 ms 2392 KB Output is correct
3 Correct 1 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 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 1 ms 12632 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Incorrect 2 ms 10584 KB Output isn't correct
12 Halted 0 ms 0 KB -