oj.uz

Submission #891831

# Submission time Handle Problem Language Result Execution time Memory
891831 2023-12-24T07:27:47 Z Vvnx Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 73 ms 309072 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);
		}
	}
	if(r > (n+1)/2 || g > (n+1)/2 || b > (n+1)/2) {
		cout << -1 << endl;
		return 0;
	}
	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 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 1 ms 12764 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 1 ms 10588 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 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 1 ms 12764 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 1 ms 10588 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 73 ms 277192 KB Output is correct
3 Correct 49 ms 276828 KB Output is correct
4 Correct 49 ms 278548 KB Output is correct
5 Correct 47 ms 279632 KB Output is correct
6 Correct 48 ms 278352 KB Output is correct
7 Correct 48 ms 277588 KB Output is correct
8 Correct 47 ms 277692 KB Output is correct
9 Correct 47 ms 278608 KB Output is correct
10 Correct 51 ms 304720 KB Output is correct
11 Correct 53 ms 309072 KB Output is correct
12 Correct 19 ms 197468 KB Output is correct
13 Correct 26 ms 257112 KB Output is correct
14 Correct 34 ms 276564 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

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