Submission #1149544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149544		AHOKA	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	201 ms	524336 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define ppp pair<int, pii>

const int maxn = 1e6 + 10, maxm = 4e2 + 1, oo = 1e9;

int n, a[maxm], dp[maxm][maxm][maxm][3], c[3], ind[3][maxm], pre[3][maxm];

signed main(){
    cin >> n;
    string st;
    cin >> st;
    st = "a" + st;
    for (int i = 1; i <= n; i++){   
        if(st[i] == 'R')
            a[i] = 0;
        else if(st[i] == 'G')
            a[i] = 1;
        else
            a[i] = 2;

        ind[a[i]][++c[a[i]]] = i;

        for (int j = 0; j < 3;j++)
            pre[j][i] = c[j];

    }

    for (int i = 0; i <= n;i++)
        for (int j = 0; j <= c[0];j++)
            for (int k = 0; k <= c[1];k++)
                for (int l = 0; l < 3;l++)
                    dp[i][j][k][l] = oo;

    for (int l = 0; l < 3;l++)
        dp[0][0][0][l] = 0;

    for (int i = 1; i <= n;i++)
        for (int r = 0; r <= min(i, c[0]);r++)
            for (int g = 0; g <= min(i - r, c[1]);g++){
                int b = i - r - g;

                if(b > c[2])
                    continue;

                if(r > 0)
                    dp[i][r][g][0] = min(dp[i - 1][r - 1][g][1], dp[i - 1][r - 1][g][2]) + max(0, g - pre[1][ind[0][r]]) + max(0, b - pre[2][ind[0][r]]);

                if(g > 0)
                    dp[i][r][g][1] = min(dp[i - 1][r][g - 1][0], dp[i - 1][r][g - 1][2]) + max(0, r - pre[0][ind[1][g]]) + max(0, b - pre[2][ind[1][g]]);

                if(b > 0)
                    dp[i][r][g][2] = min(dp[i - 1][r][g][0], dp[i - 1][r][g][1]) + max(0, r - pre[0][ind[2][b]]) + max(0, g - pre[1][ind[2][b]]);
            }

    int ans = min({dp[n][c[0]][c[1]][0], dp[n][c[0]][c[1]][1], dp[n][c[0]][c[1]][2]});
    cout << (ans >= oo ? -1 : ans);
}

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