Submission #1287566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287566		dex111222333444555	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	405 ms	780444 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
const int MAXN = 405;
using namespace std;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int lenS, s[MAXN], dp[3][MAXN][MAXN][MAXN], pre[3][MAXN], pos[3][MAXN], freq[3], infINT = 1e9 + 712823;

int id(const char &c){
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    return 2;
}

void input(){
    cin >> lenS;
    for(int i = 1; i <= lenS; i++){
        char c; cin >> c;
        s[i] = id(c);
    }
}

void init(){
    for(int i = 1; i <= lenS; i++){
        freq[s[i]]++;
        pos[s[i]][freq[s[i]]] = i;
        for(int type = 0; type < 3; type++)
            pre[type][i] = freq[type];
    }
}

int get(int c1, int c2){
    return c1 ^ c2 ^ 1 ^ 2 ^ 0;
}

int getRange(int type, int L, int R){
    if (L > R) return 0;
    return pre[type][R] - pre[type][L];
}

void solve(){
    init();
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < 3; i++) dp[i][0][0][0] = 0;
    for(int i = 0; i <= freq[0]; i++)
    for(int j = 0; j <= freq[1]; j++)
    for(int k = 0; k <= freq[2]; k++)
    for(int last = 0; last < 3; last++) if (dp[last][i][j][k] < infINT)
    for(int nxt = 0; nxt < 3; nxt++) if (last != nxt){
        int other = get(last, nxt);
        int idLast = (last == 0 ? i: (last == 1 ? j: k));
        int idNxt = (nxt == 0 ? i: (nxt == 1 ? j: k)) + 1;
        int idOther = (other == 0 ? i: (other == 1 ? j: k));
        int posLast = pos[last][idLast];
        int posNxt = pos[nxt][idNxt];
        int posOther = pos[other][idOther];
        int cost = getRange(last, posLast, posNxt) + getRange(other, posOther, posNxt);
        minimize(dp[nxt][i + (nxt == 0)][j + (nxt == 1)][k + (nxt == 2)], dp[last][i][j][k] + cost);
    }
    int res = infINT;
    for(int i = 0; i < 3; i++) minimize(res, dp[i][freq[0]][freq[1]][freq[2]]);
    cout << (res < infINT ? res: -1) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solve();
}

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