oj.uz

Submission #892116

# Submission time Handle Problem Language Result Execution time Memory
892116 2023-12-24T23:09:38 Z AMnu Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 44 ms 341076 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<pii> 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(pii(g,b));
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(pii(r,b));
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(pii(r,g));
		}
	}
	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<3; 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]) + max(0,pos[0][i-1].fi-j) + max(0,pos[0][i-1].se-k);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + max(0,pos[1][j-1].fi-i) + max(0,pos[1][j-1].se-k);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + max(0,pos[2][k-1].fi-i) + max(0,pos[2][k-1].se-j);
			}
		}
	}
	ll ans = min(dp[r][g][b][0],min(dp[r][g][b][1],dp[r][g][b][2]));
	if(ans == INF) cout << -1 << endl;
	else cout << ans << 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 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 14684 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12776 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 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 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 14684 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12776 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 41 ms 338712 KB Output is correct
3 Correct 41 ms 339536 KB Output is correct
4 Correct 44 ms 341076 KB Output is correct
5 Correct 42 ms 341072 KB Output is correct
6 Correct 41 ms 341072 KB Output is correct
7 Correct 40 ms 339028 KB Output is correct
8 Correct 40 ms 340464 KB Output is correct
9 Correct 41 ms 338940 KB Output is correct
10 Correct 42 ms 339792 KB Output is correct
11 Correct 40 ms 339796 KB Output is correct
12 Correct 19 ms 197388 KB Output is correct
13 Correct 26 ms 263184 KB Output is correct
14 Correct 30 ms 311024 KB Output is correct
15 Correct 41 ms 339164 KB Output is correct
16 Correct 41 ms 339284 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 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 14684 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12776 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -