Submission #587039

#	Time	Username	Problem	Language	Result	Execution time	Memory
587039		Justin1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	1092 ms	163492 KiB

joi2019_ho_t3

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

int n,m,k,x,y,z;
int dp[405][405][405][5];
int pos[405][5], cnt[5];
int val['z'];
char ar[405];

void cal(int r, int g, int y, int l) {
    bool debug = 0;
    if (r == 2 && !g && y == 1 && l == 2) debug = 1;
    if (r > cnt[1] + (l == 1)) return;
    if (g > cnt[2] + (l == 2)) return;
    if (y > cnt[3] + (l == 3)) return;
    int cur = pos[(l == 1 ? r : (l == 2 ? g : y))+1][l];
    int R = 0, G = 0, Y = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == cur) continue;
        if (ar[i] == 'R' && r) {
            r--;
            R++;
            if (i > cur) ans++;
        } else if (ar[i] == 'G' && g) {
            g--;
            G++;
            if (i > cur) ans++;
        } else if (ar[i] == 'Y' && y) {
            y--;
            Y++;
            if (i > cur) ans++;
        }
    }
    if (r || g || y) return;
    int tmp = 1e9;
    if (R && l != 1) tmp = min(tmp,dp[R-1][G][Y][1]);
    if (G && l != 2) tmp = min(tmp,dp[R][G-1][Y][2]);
    if (Y && l != 3) tmp = min(tmp,dp[R][G][Y-1][3]);
    if (!R && !G && !Y) tmp = 0;
    dp[R][G][Y][l] = ans + tmp;
}

int main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    val['R'] = 1, val['G'] = 2, val['Y'] = 3;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> ar[i];
    for (int i = 1; i <= n; i++) {
        cnt[val[ar[i]]]++;
        pos[cnt[val[ar[i]]]][val[ar[i]]] = i;
    }
    for (int r = 0; r <= cnt[1]; r++) {
        for (int g = 0; g <= cnt[2]; g++) {
            for (int y = 0; y <= cnt[3]; y++) {
                for (int l = 1; l <= 3; l++) {
                    dp[r][g][y][l] = 1e9;
                    cal(r,g,y,l);
                }
            }
        }
    }
    int tmp = 1e9;
    if (cnt[1]) tmp = min(tmp,dp[cnt[1]-1][cnt[2]][cnt[3]][1]);
    if (cnt[2]) tmp = min(tmp,dp[cnt[1]][cnt[2]-1][cnt[3]][2]);
    if (cnt[3]) tmp = min(tmp,dp[cnt[1]][cnt[2]][cnt[3]-1][3]);
    if (tmp >= 1e8) cout << "-1\n";
    else cout << tmp << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void cal(int, int, int, int)':
joi2019_ho_t3.cpp:12:10: warning: variable 'debug' set but not used [-Wunused-but-set-variable]
   12 |     bool debug = 0;
      |          ^~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:50:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         cnt[val[ar[i]]]++;
      |                 ~~~~^
joi2019_ho_t3.cpp:51:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |         pos[cnt[val[ar[i]]]][val[ar[i]]] = i;
      |                     ~~~~^
joi2019_ho_t3.cpp:51:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |         pos[cnt[val[ar[i]]]][val[ar[i]]] = i;
      |                                  ~~~~^

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