Submission #768139

#	Time	Username	Problem	Language	Result	Execution time	Memory
768139		1bin	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	63 ms	162956 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
int n, dp[401][401][401][3], sz[3], cnt[401][3];
vector<int> v[3];
string s, t = "RGY";

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> s;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++)
            if(s[i] == t[j]) v[j].emplace_back(i);
    for(int i = 0; i < 3; i++) sz[i] = v[i].size();
    for(int i = 0; i < 3; i++) if(s[0] == t[i]) cnt[0][i] = 1;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 3; j++) cnt[i][j] = cnt[i - 1][j] + (s[i] == t[j]);
    }
    
    for(int i = 0; i <= sz[0]; i++)
        for(int j = 0; j <= sz[1]; j++)
            for(int k = 0; k <= sz[2]; k++) 
                for(int l = 0; l < 3; l++) dp[i][j][k][l] = 1e9;
    for(int i = 0; i < 3; i++) dp[0][0][0][i] = 0;
    for(int i = 0; i <= sz[0]; i++)
        for(int j = 0; j <= sz[1]; j++)
            for(int k = 0; k <= sz[2]; k++){
                if(i + j + k){
                    if(i) dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + max(j - cnt[v[0][i - 1]][1], 0) + max(k - cnt[v[0][i - 1]][2], 0);
                    if(j) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + max(i - cnt[v[1][j - 1]][0], 0) + max(k - cnt[v[1][j - 1]][2], 0);
                    if(k) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + max(i - cnt[v[2][k - 1]][0], 0) + max(j - cnt[v[2][k - 1]][1], 0);
                }
            }
    int ans = 1e9;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
    if(ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}

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