oj.uz

Submission #936660

# Submission time Handle Problem Language Result Execution time Memory
936660 2024-03-02T12:54:30 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 65 ms 249940 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define inf ((int)1e9)
using namespace std;
const int N = 403;
int dp[N][N][N][3];

int32_t main(){
	fast
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt[3] = {0, 0, 0};
	vector <vector<int> > pos(3);
	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') {
			cnt[0]++;
			pos[0].push_back(i);
		}
		else if(s[i] == 'G') {
			cnt[1]++;
			pos[1].push_back(i);
		}
		else {
			cnt[2]++;
			pos[2].push_back(i);
		}
	}
	pos[0].push_back(inf);
	pos[1].push_back(inf);
	pos[2].push_back(inf);
	for(int r = 0; r <= cnt[0]; r++)
		for(int g = 0; g <= cnt[1]; g++)
			for(int y = 0; y <= cnt[2]; y++)
				for(int last = 0; last < 3; last++)
					dp[r][g][y][last] = inf;

	dp[1][0][0][0] = pos[0][0];
	dp[0][1][0][1] = pos[1][0];
	dp[0][0][1][2] = pos[2][0];
	for(int r = 0; r <= cnt[0]; r++) {
		int ir = pos[0][r];
		for(int g = 0; g <= cnt[1]; g++) {
			int ig = pos[1][g];
			for(int y = 0; y <= cnt[2]; y++) {
				int iy = pos[2][y];
				int ind = r + g + y;
				for(int last : {0, 1, 2}) {
					int val = dp[r][g][y][last];
					if(val >= inf) continue;
					//cout << r << " " << g << " " << y << "\n";
					//cout << ir << " " << ig << " " << iy << " " << ind << "\n";
					//cout << val << "\n";
					if(last != 0) {
						dp[r+1][g][y][0] = min(dp[r+1][g][y][0], val + abs(ir - ind));
					}
					if(last != 1) {
						dp[r][g+1][y][1] = min(dp[r][g+1][y][1], val + abs(ig - ind));
					}
					if(last != 2) {
						dp[r][g][y+1][2] = min(dp[r][g][y+1][2], val + abs(iy - ind));
					}
				}
			}
		}
	}
	int ans = inf;
	for(int i = 0; i < 3; i++) {
		ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
	}
	if(ans == inf) cout << -1;
	else cout << ans / 2;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 10728 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 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 1 ms 10840 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 2 ms 2516 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 10728 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 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 1 ms 10840 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 65 ms 247876 KB Output is correct
3 Correct 49 ms 246100 KB Output is correct
4 Correct 55 ms 246612 KB Output is correct
5 Correct 56 ms 247760 KB Output is correct
6 Correct 49 ms 247832 KB Output is correct
7 Correct 48 ms 247012 KB Output is correct
8 Correct 51 ms 248152 KB Output is correct
9 Correct 48 ms 247784 KB Output is correct
10 Correct 51 ms 248980 KB Output is correct
11 Correct 49 ms 247744 KB Output is correct
12 Correct 21 ms 160856 KB Output is correct
13 Correct 28 ms 181524 KB Output is correct
14 Correct 37 ms 209828 KB Output is correct
15 Correct 54 ms 249940 KB Output is correct
16 Correct 52 ms 249932 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 2 ms 2516 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 10728 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 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 1 ms 10840 KB Output isn't correct
12 Halted 0 ms 0 KB -