Submission #477112

#	Time	Username	Problem	Language	Result	Execution time	Memory
477112		JovanB	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	119 ms	162932 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 400;
const int INF = 1000000000;

int ima[N+5][3];
int dp[N+5][N+5][N+5][3];
int tr[3];
int gde[3][N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    string s;
    cin >> s;
    for(auto &c : s){
        if(c == 'R') c = '0';
        else if(c == 'G') c = '1';
        else c = '2';
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<=2; j++) ima[i][j] = ima[i-1][j];
        int k = s[i-1] - '0';
        ima[i][k]++;
        ++tr[k];
        gde[k][tr[k]] = i;
    }
    for(int i=0; i<=ima[n][0]; i++) for(int j=0; j<=ima[n][1]; j++) for(int k=0; k<=ima[n][2]; k++) for(int l=0; l<=2; l++) dp[i][j][k][l] = INF;
    for(int i=0; i<=2; i++) dp[0][0][0][i] = 0;
    for(int i=0; i<=ima[n][0]; i++){
        for(int j=0; j<=ima[n][1]; j++){
            for(int k=0; k<=ima[n][2]; k++){
                for(int l=0; l<=2; l++){
                    if(i + j + k > 0){
                        if(i == 0 && l == 0) continue;
                        if(j == 0 && l == 1) continue;
                        if(k == 0 && l == 2) continue;
                    }
                    if(i < ima[n][0] && l != 0){
                        int h = gde[0][i+1];
                        dp[i+1][j][k][0] = min(dp[i+1][j][k][0], dp[i][j][k][l] + max(0, j - ima[h][1]) + max(0, k - ima[h][2]));
                    }
                    if(j < ima[n][1] && l != 1){
                        int h = gde[1][j+1];
                        dp[i][j+1][k][1] = min(dp[i][j+1][k][1], dp[i][j][k][l] + max(0, i - ima[h][0]) + max(0, k - ima[h][2]));
                    }
                    if(k < ima[n][2] && l != 2){
                        int h = gde[2][k+1];
                        dp[i][j][k+1][2] = min(dp[i][j][k+1][2], dp[i][j][k][l] + max(0, i - ima[h][0]) + max(0, j - ima[h][1]));
                    }
                }
            }
        }
    }
    int g = INF;
    for(int i=0; i<=2; i++) g = min(g, dp[ima[n][0]][ima[n][1]][ima[n][2]][i]);
    cout << (g == INF ? -1 : g) << "\n";
    return 0;
}

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