oj.uz

Submission #532033

# Submission time Handle Problem Language Result Execution time Memory
532033 2022-03-02T04:06:17 Z rk42745417 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 333 ms 757600 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] = 2;
			else
				arr[i] = 1;
		}
	}
	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++) {
				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 307 ms 757356 KB Output is correct
2 Correct 319 ms 757332 KB Output is correct
3 Correct 273 ms 757316 KB Output is correct
4 Correct 289 ms 757324 KB Output is correct
5 Correct 300 ms 757312 KB Output is correct
6 Correct 299 ms 757372 KB Output is correct
7 Correct 283 ms 757600 KB Output is correct
8 Correct 286 ms 757300 KB Output is correct
9 Correct 278 ms 757316 KB Output is correct
10 Correct 303 ms 757316 KB Output is correct
11 Correct 273 ms 757316 KB Output is correct
12 Correct 296 ms 757320 KB Output is correct
13 Incorrect 291 ms 757364 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 757356 KB Output is correct
2 Correct 319 ms 757332 KB Output is correct
3 Correct 273 ms 757316 KB Output is correct
4 Correct 289 ms 757324 KB Output is correct
5 Correct 300 ms 757312 KB Output is correct
6 Correct 299 ms 757372 KB Output is correct
7 Correct 283 ms 757600 KB Output is correct
8 Correct 286 ms 757300 KB Output is correct
9 Correct 278 ms 757316 KB Output is correct
10 Correct 303 ms 757316 KB Output is correct
11 Correct 273 ms 757316 KB Output is correct
12 Correct 296 ms 757320 KB Output is correct
13 Incorrect 291 ms 757364 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 294 ms 757412 KB Output is correct
2 Correct 294 ms 757372 KB Output is correct
3 Correct 296 ms 757500 KB Output is correct
4 Correct 333 ms 757392 KB Output is correct
5 Correct 275 ms 757408 KB Output is correct
6 Correct 291 ms 757408 KB Output is correct
7 Correct 275 ms 757384 KB Output is correct
8 Correct 282 ms 757340 KB Output is correct
9 Correct 306 ms 757468 KB Output is correct
10 Correct 280 ms 757392 KB Output is correct
11 Correct 295 ms 757444 KB Output is correct
12 Correct 274 ms 757388 KB Output is correct
13 Correct 295 ms 757300 KB Output is correct
14 Correct 282 ms 757400 KB Output is correct
15 Correct 288 ms 757316 KB Output is correct
16 Correct 279 ms 757412 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 757356 KB Output is correct
2 Correct 319 ms 757332 KB Output is correct
3 Correct 273 ms 757316 KB Output is correct
4 Correct 289 ms 757324 KB Output is correct
5 Correct 300 ms 757312 KB Output is correct
6 Correct 299 ms 757372 KB Output is correct
7 Correct 283 ms 757600 KB Output is correct
8 Correct 286 ms 757300 KB Output is correct
9 Correct 278 ms 757316 KB Output is correct
10 Correct 303 ms 757316 KB Output is correct
11 Correct 273 ms 757316 KB Output is correct
12 Correct 296 ms 757320 KB Output is correct
13 Incorrect 291 ms 757364 KB Output isn't correct
14 Halted 0 ms 0 KB -