제출 #236977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236977		Atalasion	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	469 ms	809848 KiB

joi2019_ho_t3

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 400 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, dp[N][N][N][3], koj[3][N], a[N], ps[3][N], num[3];
string s;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++){
		if (s[i - 1] == 'R') a[i] = 0;
		else if(s[i - 1] == 'G') a[i] = 1;
		else a[i] = 2;
	}
	for (int i = 0; i < 3; i++){
		int cnt = 0;
		for (int j = 1; j <= n; j++) if (a[j] == i) koj[i][++cnt] = j, ps[i][j] ++;
		for (int j = 1; j <= n; j++) ps[i][j] += ps[i][j - 1];
		num[i] = cnt;
	}
	memset(dp, 31, sizeof dp);
	dp[1][0][0][0] = dp[0][1][0][1] = dp[0][0][1][2] = 0;
	for (int i = 0; i <= num[0]; i++)for (int j = 0; j <= num[1]; j++)for (int k = 0; k <= num[2]; k++){
		if (i + j + k <= 1) continue;
		int x = koj[0][i], y = koj[1][j], z = koj[2][k];
		int mv = 0;
		if (i > 0){
			if (y > x) mv += ps[1][y] - ps[1][x];
			if (z > x) mv += ps[2][z] - ps[2][x];
			dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + mv;
		}
		mv = 0;
		if (j > 0){
			if (x > y) mv += ps[0][x] - ps[0][y];
			if (z > y) mv += ps[2][z] - ps[2][y];
			dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + mv;
		}
		mv = 0;
		if (k > 0){
			if (x > z) mv += ps[0][x] - ps[0][z];
			if (y > z) mv += ps[1][y] - ps[1][z];
			dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]) + mv;
		}
//		cout << i << ' ' << j << ' ' << ' ' << k << ' ' << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << ' ' << dp[i][j][k][2] << '\n';
	}
	int res = min({dp[num[0]][num[1]][num[2]][0], dp[num[0]][num[1]][num[2]][1], dp[num[0]][num[1]][num[2]][2]});
	cout << (res > n * n?-1:res);




	return 0;
}

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