제출 #207093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207093		cheissmart	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	556 ms	774776 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 404;

int dp[N][N][N][3], a[N], cnt[N][3];
vi occ[3];

signed main()
{
	IO_OP;
	
	int n;
	string s;
	cin >> n >> s;
	for(int i=0;i<n;i++) {
		a[i+1] = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
		occ[a[i+1]].PB(i+1);
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<3;j++) cnt[i][j] = cnt[i-1][j];
		cnt[i][a[i]]++;
	}
	memset(dp, 0x3f, sizeof dp);
	for(int i=0;i<=cnt[n][0];i++) {
		for(int j=0;j<=cnt[n][1];j++) {
			for(int k=0;k<=cnt[n][2];k++) {
				if(i == 0 && j == 0 && k == 0) {
					for(int l=0;l<3;l++)
						dp[i][j][k][l] = 0;
				} else {
					for(int l=0;l<3;l++) {
						int pos, jump, pre_dp;
						if(l == 0) {
							if(i == 0) continue;
							pre_dp = min(dp[i-1][j][k][1], dp[i-1][j][k][2]);
							pos = occ[l][i-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - (i-1));
							jump += max(0, cnt[pos-1][1] - j);
							jump += max(0, cnt[pos-1][2] - k);
						} else if(l == 1) {
							if(j == 0) continue;
							pre_dp = min(dp[i][j-1][k][0], dp[i][j-1][k][2]);
							pos = occ[l][j-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - i);
							jump += max(0, cnt[pos-1][1] - (j-1));
							jump += max(0, cnt[pos-1][2] - k);
						} else {
							if(k == 0) continue;
							pre_dp = min(dp[i][j][k-1][0], dp[i][j][k-1][1]);
							pos = occ[l][k-1];
							jump = 0;
							jump += max(0, cnt[pos-1][0] - i);
							jump += max(0, cnt[pos-1][1] - j);
							jump += max(0, cnt[pos-1][2] - (k-1));
						}
						dp[i][j][k][l] = min(dp[i][j][k][l], pre_dp + jump);
					}
				}
			}
		}
	}
	int ans = INF;
	for(int i=0;i<3;i++)
		ans = min(ans, dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][i]);
	if(ans > 1e8) ans = -1;
	cout << ans << endl;

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25