oj.uz

Submission #532027

# Submission time Handle Problem Language Result Execution time Memory
532027 2022-03-02T04:00:26 Z rk42745417 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 320 ms 757532 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(4e15) + ll(2e15);
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 401;
int dp[N][N][N][3];

signed main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	{
		string s;
		cin >> s;
		for(int i = 0; i < n; i++) {
			if(s[i] == 'R')
				arr[i] = 0;
			else if(s[i] == 'G')
				arr[i] = 1;
			else
				arr[i] = 2;
		}
	}
	array<vector<int>, 3> pos;
	vector<array<int, 3>> cnt(n);
	for(int i = 0; i < n; i++) {
		pos[arr[i]].push_back(i);
		cnt[i][arr[i]]++;
		if(i) {
			for(int j = 0; j < 3; j++)
				cnt[i][j] += cnt[i - 1][j];
		}
	}
	int a = pos[0].size(), b = pos[1].size(), c = pos[2].size();
	memset(dp, 0x3f, sizeof dp);
	for(int i = 0; i < 3; i++)
		dp[0][0][0][i] = 0;

	for(int i = 0; i <= a; i++) {
		for(int j = 0; j <= b; j++) {
			for(int k = 0; k <= c; k++) {
				//cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << ' ' << dp[i][j][k][2] << '\n';
				if(i < a) {
					int cost = max(0, cnt[pos[0][i]][1] - j) + max(0, cnt[pos[0][i]][2] - k);
					dp[i + 1][j][k][0] = min(dp[i][j][k][1] + cost, dp[i][j][k][2] + cost);
				}
				if(j < b) {
					int cost = max(0, cnt[pos[1][j]][0] - i) + max(0, cnt[pos[1][j]][2] - k);	
					dp[i][j + 1][k][1] = min(dp[i][j][k][0] + cost, dp[i][j][k][2] + cost);
				}
				if(k < c) {
					int cost = max(0, cnt[pos[2][k]][0] - i) + max(0, cnt[pos[2][k]][1] - j);
					dp[i][j][k + 1][2] = min(dp[i][j][k][0] + cost, dp[i][j][k][1] + cost);
				}
			}
		}
	}

	int r = min({dp[a][b][c][0], dp[a][b][c][1], dp[a][b][c][2]});
	if(r == INF)
		cout << "-1\n";
	else
		cout << r << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 757300 KB Output is correct
2 Correct 290 ms 757308 KB Output is correct
3 Correct 297 ms 757400 KB Output is correct
4 Correct 309 ms 757336 KB Output is correct
5 Correct 294 ms 757428 KB Output is correct
6 Correct 301 ms 757340 KB Output is correct
7 Correct 295 ms 757316 KB Output is correct
8 Correct 308 ms 757288 KB Output is correct
9 Correct 296 ms 757292 KB Output is correct
10 Correct 304 ms 757328 KB Output is correct
11 Correct 314 ms 757292 KB Output is correct
12 Correct 297 ms 757284 KB Output is correct
13 Incorrect 287 ms 757316 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 757300 KB Output is correct
2 Correct 290 ms 757308 KB Output is correct
3 Correct 297 ms 757400 KB Output is correct
4 Correct 309 ms 757336 KB Output is correct
5 Correct 294 ms 757428 KB Output is correct
6 Correct 301 ms 757340 KB Output is correct
7 Correct 295 ms 757316 KB Output is correct
8 Correct 308 ms 757288 KB Output is correct
9 Correct 296 ms 757292 KB Output is correct
10 Correct 304 ms 757328 KB Output is correct
11 Correct 314 ms 757292 KB Output is correct
12 Correct 297 ms 757284 KB Output is correct
13 Incorrect 287 ms 757316 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 290 ms 757404 KB Output is correct
2 Correct 298 ms 757528 KB Output is correct
3 Correct 286 ms 757368 KB Output is correct
4 Correct 295 ms 757444 KB Output is correct
5 Correct 286 ms 757368 KB Output is correct
6 Correct 285 ms 757396 KB Output is correct
7 Correct 291 ms 757532 KB Output is correct
8 Correct 288 ms 757320 KB Output is correct
9 Correct 289 ms 757336 KB Output is correct
10 Correct 283 ms 757316 KB Output is correct
11 Correct 301 ms 757408 KB Output is correct
12 Correct 297 ms 757316 KB Output is correct
13 Correct 287 ms 757308 KB Output is correct
14 Correct 290 ms 757316 KB Output is correct
15 Correct 286 ms 757320 KB Output is correct
16 Correct 296 ms 757316 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 757300 KB Output is correct
2 Correct 290 ms 757308 KB Output is correct
3 Correct 297 ms 757400 KB Output is correct
4 Correct 309 ms 757336 KB Output is correct
5 Correct 294 ms 757428 KB Output is correct
6 Correct 301 ms 757340 KB Output is correct
7 Correct 295 ms 757316 KB Output is correct
8 Correct 308 ms 757288 KB Output is correct
9 Correct 296 ms 757292 KB Output is correct
10 Correct 304 ms 757328 KB Output is correct
11 Correct 314 ms 757292 KB Output is correct
12 Correct 297 ms 757284 KB Output is correct
13 Incorrect 287 ms 757316 KB Output isn't correct
14 Halted 0 ms 0 KB -