oj.uz

Submission #370359

# Submission time Handle Problem Language Result Execution time Memory
370359 2021-02-23T20:57:37 Z shivensinha4 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 393 ms 757740 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; string s; cin >> n >> s;
	vi nums(n);
	vector<vi> cpos(3);
	for_(i, 0, n) {
		if (s[i] == 'G') nums[i] = 1;
		else if (s[i] == 'Y') nums[i] = 2;
		cpos[nums[i]].push_back(i);
	}
	
	const int INF = 1e9;
	int dp[n+1][n+1][n+1][3], t[3], ct[3];
	memset(dp, 0x3f, sizeof(dp));
	
	for_(i, 0, 3) ct[i] = cpos[i].size();
	
	int ans;
	for (int i = n; i >= 0; i--) for (t[0] = 0; t[0] < min(ct[0], i) + 1; t[0]++) for (t[1] = 0; t[1] < min(ct[1], i-t[0]) + 1; t[1]++) {
		t[2] = i-t[0]-t[1];
		if (t[2] > ct[2]) continue;
		for_(last, 0, 3) {
			ans = INF;
			if (i == n) {
				ans = (t[0] == ct[0] and t[1] == ct[1] and t[2] == ct[2]) ? 0 : INF;
			}
			else for_(c, 0, 3) if (c != last and ct[c] > t[c]) {
				ans = min(ans, dp[i+1][t[0]+(c==0)][t[1]+(c==1)][c] + max(i, cpos[c][t[c]]) - i);
			}
			
			dp[i][t[0]][t[1]][last] = ans;
		}
	}
	
	ans = min({dp[0][0][0][1], dp[0][0][0][0]});
	
	cout << (ans >= INF ? -1 : ans) << endl;
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 380 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 364 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 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 380 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 364 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 384 KB Output is correct
2 Correct 388 ms 757612 KB Output is correct
3 Correct 383 ms 751852 KB Output is correct
4 Correct 382 ms 757484 KB Output is correct
5 Correct 386 ms 757740 KB Output is correct
6 Correct 393 ms 757468 KB Output is correct
7 Correct 381 ms 751852 KB Output is correct
8 Correct 381 ms 751852 KB Output is correct
9 Correct 377 ms 746220 KB Output is correct
10 Correct 383 ms 757484 KB Output is correct
11 Correct 381 ms 757484 KB Output is correct
12 Correct 54 ms 104428 KB Output is correct
13 Correct 126 ms 244460 KB Output is correct
14 Correct 217 ms 426092 KB Output is correct
15 Correct 385 ms 757472 KB Output is correct
16 Correct 386 ms 757588 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 380 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Halted 0 ms 0 KB -