Submission #988344

#	Time	Username	Problem	Language	Result	Execution time	Memory
988344		biximo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	414 ms	519360 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define N 405
#define INF 2000000000
using namespace std;
int n, dp[N][N][N][4], p[N][3];
string s;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    for(char&i: s) {
    	if(i=='R')i=0;
    	else if(i == 'G')i=1;
    	else i=2;
    }
    for(int i = 1; i <= n; i ++) {
    	for(int j = 0; j < 3; j ++) {
    		p[i][j] = p[i-1][j]+(s[i-1]==j);
    	}
    }
    for(int i = 0; i <= n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 4; l ++) {
    				dp[i][j][k][l] = INF;
    			}
    		}
    	}
    }
    dp[0][0][0][3] = 0;
    for(int i = 0; i < n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 3+(i==0); l ++) {
    				if(INF == dp[i][j][k][l]) continue;
    				for(int nl = 0; nl < 3; nl ++) {
    					if(l == nl) continue;
    					int nj = j, nk = k;
    					if(nl == 0) nj++;
    					else if(nl == 1) nk++;
    					int nc = dp[i][j][k][l]+(abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))/2;
    					dp[i+1][nj][nk][nl] = min(dp[i+1][nj][nk][nl],nc);
    					assert((abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))%2==0);
    				}
    			}
    		}
    	}
    }
    int ans = INF;
    for(int i = 0; i < 3; i ++) {
    	ans = min(ans, dp[n][p[n][0]][p[n][1]][i]);
    }
    // assert(ans%2==0);
    if(ans == INF) cout << "-1";
    else cout << ans;
}

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