oj.uz

Submission #370358

# Submission time Handle Problem Language Result Execution time Memory
370358 2021-02-23T20:55:09 Z shivensinha4 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 413 ms 753772 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][n][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 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 386 ms 753700 KB Output is correct
3 Correct 386 ms 748012 KB Output is correct
4 Correct 389 ms 753680 KB Output is correct
5 Correct 394 ms 753772 KB Output is correct
6 Correct 386 ms 753772 KB Output is correct
7 Correct 406 ms 748012 KB Output is correct
8 Correct 410 ms 748012 KB Output is correct
9 Correct 393 ms 742764 KB Output is correct
10 Correct 387 ms 753644 KB Output is correct
11 Correct 385 ms 753644 KB Output is correct
12 Correct 55 ms 103532 KB Output is correct
13 Correct 125 ms 242796 KB Output is correct
14 Correct 216 ms 423788 KB Output is correct
15 Correct 413 ms 753772 KB Output is correct
16 Correct 385 ms 753744 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -