Submission #256395

#	Time	Username	Problem	Language	Result	Execution time	Memory
256395		Osama_Alkhodairy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	507 ms	757624 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 401;

int n, dp[N][N][N][3], sum[N][3], pos[N][3];
string s;

int get_sum(int idx, int l, int r){
    if(r < l || l == -1 || r == -1) return 0;
    return sum[r][idx] - (l == 0 ? 0 : sum[l - 1][idx]);
}
int solve(int a, int b, int c, int las){
    if(a + b + c == n) return 0;
    int &ret = dp[a][b][c][las];
    if(ret != -1) return ret;
    ret = 1e9;
    if((las != 0 || a + b + c == 0) && pos[a][0] != -1){
        ret = min(ret, solve(a + 1, b, c, 0) + get_sum(1, pos[b][1], pos[a][0]) + get_sum(2, pos[c][2], pos[a][0]));
    }
    if((las != 1 || a + b + c == 0) && pos[b][1] != -1){
        ret = min(ret, solve(a, b + 1, c, 1) + get_sum(0, pos[a][0], pos[b][1]) + get_sum(2, pos[c][2], pos[b][1]));
    }
    if((las != 2 || a + b + c == 0) && pos[c][2] != -1){
        ret = min(ret, solve(a, b, c + 1, 2) + get_sum(0, pos[a][0], pos[c][2]) + get_sum(1, pos[b][1], pos[c][2]));
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(pos, -1, sizeof pos);
    memset(dp, -1, sizeof dp);
    cin >> n >> s;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 'R') s[i] = 0;
        else if(s[i] == 'G') s[i] = 1;
        else s[i] = 2;
        for(int j = 0 ; j < 3 ; j++){
            if(i > 0) sum[i][j] = sum[i - 1][j];
            sum[i][j] += s[i] == j;
        }
    }
    int pt0 = 0, pt1 = 0, pt2 = 0;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 0) pos[pt0++][0] = i;
        else if(s[i] == 1) pos[pt1++][1] = i;
        else pos[pt2++][2] = i;
    }
    int ans = solve(0, 0, 0, 0);
    if(ans == 1e9) ans = -1;
    cout << ans << endl;
}

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