oj.uz

Submission #370360

# Submission time Handle Problem Language Result Execution time Memory
370360 2021-02-23T20:58:34 Z shivensinha4 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 474 ms 757628 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);
//				if (i == 2 and t[0] == 1 and t[1] == 1 and last == 1 and dp[i+1][t[0]+(c==0)][t[1]+(c==1)][c] + max(i, cpos[c][t[c]]) - i == 0)
//					cout << "..." << i+1 << " " << (t[0]+(c==0)) << " " << (t[1]+(c==1)) << " " << c << endl;
			}
			
			dp[i][t[0]][t[1]][last] = ans;
		}
	}
	
//	cout << dp[0][0][0][1] << " " << dp[1][1][0][0] << " " << dp[2][1][1][1] << " " << dp[3][2][1][0] << endl;
	ans = min({dp[0][0][0][1], dp[0][0][0][0], dp[0][0][0][2]});
	
	cout << (ans >= INF ? -1 : ans) << endl;
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 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 0 ms 364 KB Output is correct
2 Correct 474 ms 757492 KB Output is correct
3 Correct 387 ms 751852 KB Output is correct
4 Correct 394 ms 757448 KB Output is correct
5 Correct 429 ms 757388 KB Output is correct
6 Correct 394 ms 757612 KB Output is correct
7 Correct 392 ms 751852 KB Output is correct
8 Correct 394 ms 751816 KB Output is correct
9 Correct 409 ms 746420 KB Output is correct
10 Correct 395 ms 757484 KB Output is correct
11 Correct 392 ms 757384 KB Output is correct
12 Correct 59 ms 104428 KB Output is correct
13 Correct 138 ms 244588 KB Output is correct
14 Correct 241 ms 426220 KB Output is correct
15 Correct 405 ms 757628 KB Output is correct
16 Correct 400 ms 757612 KB Output is correct

Subtask #4
0 / 25.0

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