oj.uz

Submission #1000257

# Submission time Handle Problem Language Result Execution time Memory
1000257 2024-06-17T07:27:24 Z biximo Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 473 ms 1040536 KB 
#include <bits/stdc++.h>
#define N 405
#define INF 2000000000
using namespace std;
int n,dp[N][N][N][4], rs[N], gs[N], ys[N];
string s;
int cost(int r, int g, int y, int i) {
	return abs(rs[i]-r)+abs(gs[i]-g)+abs(ys[i]-y);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
   	cin >> n >> s;
   	for(int i = 1; i <= n; i ++) {
   		rs[i] = rs[i-1]+(s[i-1]=='R');
   		gs[i] = gs[i-1]+(s[i-1]=='G');
   		ys[i] = ys[i-1]+(s[i-1]=='Y');
   	}
   	for(auto&i: dp) for(auto&j: i) for(auto&k: j) for(auto&l: k) l = INF;
   	dp[0][0][0][0] = 0;
   	for(int i = 0; i < n; i ++) {
   		for(int r = 0; r <= i && r <= rs[n]; r ++) {
   			for(int g = 0; r+g <= i && g <= gs[n]; g ++) {
   				int y = i-r-g;
   				if(y > ys[n]) continue;
   				for(int t = (i!=0); t <= 3; t ++) {
	   				if(t != 1)
	   				dp[i+1][r+1][g][1] = min(dp[i+1][r+1][g][1],dp[i][r][g][t]+cost(r+1,g,y,i+1));
	   				if(t != 2)
	   				dp[i+1][r][g+1][2] = min(dp[i+1][r][g+1][2],dp[i][r][g][t]+cost(r,g+1,y,i+1));
	   				if(t != 3)
	   				dp[i+1][r][g][3] = min(dp[i+1][r][g][3],dp[i][r][g][t]+cost(r,g,y+1,i+1));
   				}
   			}
   		}
   	}
   	int res = min({dp[n][rs[n]][gs[n]][1],dp[n][rs[n]][gs[n]][2],dp[n][rs[n]][gs[n]][3]})/2;
   	if(res == INF/2) cout << -1;
   	else cout << res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 1040432 KB Output is correct
2 Correct 319 ms 1040352 KB Output is correct
3 Correct 315 ms 1040464 KB Output is correct
4 Correct 345 ms 1040336 KB Output is correct
5 Correct 348 ms 1040208 KB Output is correct
6 Correct 345 ms 1040364 KB Output is correct
7 Correct 348 ms 1040240 KB Output is correct
8 Correct 340 ms 1040208 KB Output is correct
9 Correct 345 ms 1040536 KB Output is correct
10 Correct 350 ms 1040372 KB Output is correct
11 Incorrect 349 ms 1040396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 1040432 KB Output is correct
2 Correct 319 ms 1040352 KB Output is correct
3 Correct 315 ms 1040464 KB Output is correct
4 Correct 345 ms 1040336 KB Output is correct
5 Correct 348 ms 1040208 KB Output is correct
6 Correct 345 ms 1040364 KB Output is correct
7 Correct 348 ms 1040240 KB Output is correct
8 Correct 340 ms 1040208 KB Output is correct
9 Correct 345 ms 1040536 KB Output is correct
10 Correct 350 ms 1040372 KB Output is correct
11 Incorrect 349 ms 1040396 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 340 ms 1040244 KB Output is correct
2 Correct 362 ms 1040440 KB Output is correct
3 Correct 335 ms 1040212 KB Output is correct
4 Correct 357 ms 1040216 KB Output is correct
5 Correct 351 ms 1040440 KB Output is correct
6 Correct 368 ms 1040396 KB Output is correct
7 Correct 355 ms 1040212 KB Output is correct
8 Correct 345 ms 1040208 KB Output is correct
9 Correct 356 ms 1040212 KB Output is correct
10 Correct 341 ms 1040204 KB Output is correct
11 Correct 344 ms 1040344 KB Output is correct
12 Correct 339 ms 1040308 KB Output is correct
13 Correct 341 ms 1040212 KB Output is correct
14 Correct 473 ms 1040212 KB Output is correct
15 Correct 349 ms 1040224 KB Output is correct
16 Correct 323 ms 1040376 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 1040432 KB Output is correct
2 Correct 319 ms 1040352 KB Output is correct
3 Correct 315 ms 1040464 KB Output is correct
4 Correct 345 ms 1040336 KB Output is correct
5 Correct 348 ms 1040208 KB Output is correct
6 Correct 345 ms 1040364 KB Output is correct
7 Correct 348 ms 1040240 KB Output is correct
8 Correct 340 ms 1040208 KB Output is correct
9 Correct 345 ms 1040536 KB Output is correct
10 Correct 350 ms 1040372 KB Output is correct
11 Incorrect 349 ms 1040396 KB Output isn't correct
12 Halted 0 ms 0 KB -