Submission #1034925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034925		ten_xd	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	6 ms	10496 KiB

joi2019_ho_t3

#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 / 5
• Subtask 2: 55 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25