oj.uz

Submission #1034925

# Submission time Handle Problem Language Result Execution time Memory
1034925 2024-07-25T21:57:47 Z ten_xd Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 6 ms 10496 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 75, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

int n;
string A;
int B[N];
int S[3][N];
vector<int> V[3];
int dp[N][N][N][3];

void solve()
{
	cin >> n >> A;
	rep(i,n)
	{
		if(A[i] == 'R') B[i] = 0;
		else if(A[i] == 'Y') B[i] = 1;
		else B[i] = 2;
	}

	rep(i,3)
	{
		int s = 0;
		rep(j,n)
		{
			S[i][j] = s;
			if(B[j] == i) ++s;
		}
	}
	rep(i,n) V[B[i]].pb(i);

	rep(i,N) rep(j,N) rep(k,N) rep(f,3) dp[i][j][k][f] = INF;

	if((int)V[0].size() > 0) dp[1][1][0][0] = V[0][0];
	if((int)V[1].size() > 0) dp[1][0][1][1] = V[1][0];
	if((int)V[2].size() > 0) dp[1][0][0][2] = V[2][0];

	for(int i = 1; i < n; ++i)
	{
		for(int A = 0; A <= n; ++A)
		{
			for(int B = 0; B <= n; ++B)
			{
				if(n-A-B < 0) continue;
				int C = i-A-B;
				int W[3];
				W[0] = A, W[1] = B, W[2] = C;
				rep(k,3)
				{
					if(dp[i][A][B][k] >= INF) continue;
					rep(f,3)
					{
						if(k == f or (int)V[f].size() <= W[f]) continue;

						int idx = V[f][W[f]], poz = 0;
						poz = idx + (max(0,W[0]-S[0][idx])) + (max(0,W[1]-S[1][idx])) + (max(0,W[2]-S[2][idx]));

						//cout << "A: " << A << " B: " << B << " C: " << C << " K: " << k << " F: " << f << " POZ: " << poz << '\n';
						int H[3];
						H[0] = W[0], H[1] = W[1], H[2] = W[2], ++H[f];
						int cost = dp[i][W[0]][W[1]][k]+(poz-i);

						//cout << '\n';
						//cout << "I: " << i << " A: " << A << " B: " << B << " C: " << C << " K: " << k << " F: " << f << " POZ: " << poz << " COST: " << cost << '\n';
						//cout << "H[0]: " << H[0] << " H[1]: " << H[1] << " H[2]: " << H[2] << '\n'; 
						//cout << '\n';

						dp[i+1][H[0]][H[1]][f] = min(dp[i+1][H[0]][H[1]][f],cost);
					}
				}
			}
		}
	}

	int wyn = INF;
	rep(i,N) rep(j,N) rep(k,3) wyn = min(wyn,dp[n][i][j][k]);

	if(wyn >= INF) cout << "-1" << '\n';
	else cout << wyn << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5336 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 2 ms 5312 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5336 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 2 ms 5312 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5304 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 3 ms 5412 KB Output is correct
28 Correct 3 ms 5208 KB Output is correct
29 Correct 2 ms 5212 KB Output is correct
30 Correct 2 ms 5212 KB Output is correct
31 Correct 3 ms 5352 KB Output is correct
32 Correct 3 ms 5212 KB Output is correct
33 Correct 2 ms 5212 KB Output is correct
34 Correct 3 ms 5212 KB Output is correct
35 Correct 3 ms 5212 KB Output is correct
36 Correct 3 ms 5212 KB Output is correct
37 Correct 3 ms 5212 KB Output is correct
38 Correct 3 ms 5328 KB Output is correct
39 Correct 3 ms 5208 KB Output is correct
40 Correct 2 ms 5212 KB Output is correct
41 Correct 2 ms 5332 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Runtime error 6 ms 10496 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5336 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 2 ms 5312 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5304 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 3 ms 5412 KB Output is correct
28 Correct 3 ms 5208 KB Output is correct
29 Correct 2 ms 5212 KB Output is correct
30 Correct 2 ms 5212 KB Output is correct
31 Correct 3 ms 5352 KB Output is correct
32 Correct 3 ms 5212 KB Output is correct
33 Correct 2 ms 5212 KB Output is correct
34 Correct 3 ms 5212 KB Output is correct
35 Correct 3 ms 5212 KB Output is correct
36 Correct 3 ms 5212 KB Output is correct
37 Correct 3 ms 5212 KB Output is correct
38 Correct 3 ms 5328 KB Output is correct
39 Correct 3 ms 5208 KB Output is correct
40 Correct 2 ms 5212 KB Output is correct
41 Correct 2 ms 5332 KB Output is correct
42 Correct 2 ms 5212 KB Output is correct
43 Runtime error 6 ms 10496 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -