제출 #163520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163520		nvmdava	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	874 ms	163092 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 405
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
 
char c[N];
int dp[N][N][N][3];
int a[N];
vector<int> app[3];
 
int i[3];

int cost(int k, int r){
	i[k]--;
	int res = dp[i[0]][i[1]][i[2]][r];
	int v = app[k][i[k]];
	i[k]++;
	int w = v;
	for(int j = 0; j < 3; j++){
		int a = upper_bound(app[j].begin(), app[j].begin() + i[j], v) - app[j].begin();
		w += max(0, i[j] - a);
	}
 
	return res + abs(i[0] + i[1] + i[2] - w);
}

int s[3];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin>>n;
 
    for(int i = 1; i <= n; i++){
    	cin>>c[i];
    	if(c[i] == 'R')
    		app[0].push_back(i);
    	else if(c[i] == 'G')
    		app[1].push_back(i);
    	else
    		app[2].push_back(i);
    }

    for(int i = 0; i < 3; ++i)
    	s[i] = app[i].size();

    for(i[0] = 0; i[0] <= s[0]; ++i[0]){
    	for(i[1] = 0; i[1] <= s[1]; ++i[1]){
    		for(i[2] = 0; i[2] <= s[2]; ++i[2]){
    			for(int k = 0; k < 3; ++k){
    				dp[i[0]][i[1]][i[2]][k] = INF;

    				if(i[0] + i[1] + i[2] == 0)
    					dp[i[0]][i[1]][i[2]][k] = 0;
    				
    				if(i[k] == 0) continue;

    				for(int r = 0; r < 3; ++r){
    					if(k == r)
    						continue;
    					dp[i[0]][i[1]][i[2]][k] = min(dp[i[0]][i[1]][i[2]][k], cost(k, r));
    				}
    			}
    		}
    	}
    }
    int res = min(dp[s[0]][s[1]][s[2]][0], min(dp[s[0]][s[1]][s[2]][1], dp[s[0]][s[1]][s[2]][2]));
    if(res == 0x3f3f3f3f)
    	cout<<-1;
    else
    	cout<<res;
}

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