Submission #499621

#	Time	Username	Problem	Language	Result	Execution time	Memory
499621		Marceantasy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	175 ms	145456 KiB

joi2019_ho_t3

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

#define ll long long
#define ar array

const int mxN = 410, M = 1e9+7; 
int n, dp[4][210][210][210], sum[3][mxN], cnt[3];
string s;
vector<int> a[3];

int solvepos(char c, int pos){
    if(c == 'R'){
        return sum[0][pos+1];
    }
    if(c == 'G'){
        return sum[1][pos+1];
    }
    return sum[2][pos+1];
}

int cost(int flag, int R, int G, int Y){
    int pos;
    if(flag == 0){
        pos = a[flag][R-1];
    }
    if(flag == 1){
        pos = a[flag][G-1];
    }
    if(flag == 2){
        pos = a[flag][Y-1];
    }
    return max(solvepos('R', pos) - R, 0) + max(solvepos('G', pos) - G, 0) + max(solvepos('Y', pos) - Y, 0);
}

int solve(int last, int R, int G, int Y){
    if(R+G+Y == 0){
        return 0;
    }
    if(~dp[last][R][G][Y]) return dp[last][R][G][Y];
    int flag = 1e9;
    if(R && last != 0){
        flag = min(flag, solve(0, R-1, G, Y) + cost(0, R, G, Y));
    }
    if(G && last != 1){
        flag = min(flag, solve(1, R, G-1, Y) + cost(1, R, G, Y));
    }
    if(Y && last != 2){
        flag = min(flag, solve(2, R, G, Y-1) + cost(2, R, G, Y));
    }
    return dp[last][R][G][Y] = flag;
}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> s;
    for(int i = n-1; i>=0; --i){
        if(s[i] == 'R'){
            cnt[0]++;
            a[0].push_back(i);
            sum[0][i]++;
        }else if(s[i] == 'G'){
            cnt[1]++;
            a[1].push_back(i);
            sum[1][i]++;
        }else{
            cnt[2]++;
            a[2].push_back(i);
            sum[2][i]++;
        }
        for(int j = 0; j<3; ++j){
            sum[j][i] += sum[j][i+1];
        }
    }
    memset(dp, -1, sizeof(dp));
    if(max(cnt[0], max(cnt[1], cnt[2])) > 202){
        cout << "-1\n";
    }else{
        int ans = solve(3, cnt[0], cnt[1], cnt[2]);
        if(ans >= 1e8){
            cout << "-1\n";
        }else{
            cout << ans << "\n";
        }
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int cost(int, int, int, int)':
joi2019_ho_t3.cpp:14:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 |         return sum[0][pos+1];
      |                       ~~~^~
joi2019_ho_t3.cpp:23:9: note: 'pos' was declared here
   23 |     int pos;
      |         ^~~

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