Submission #1344543

#TimeUsernameProblemLanguageResultExecution timeMemory
1344543khanhphucscratchGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
15 / 100
33 ms8136 KiB
#include<bits/stdc++.h>
using namespace std;
const long long lim = 1e18;
inline void chmin(long long &a, long long b)
{
    a = min(a, b);
}
vector<int> places[3];
long long dp[2][405][405][3];
signed main()
{
    ios_base::sync_with_stdio(false);
    int n; string s; cin>>n>>s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'R') places[0].push_back(i);
        if(s[i] == 'G') places[1].push_back(i);
        if(s[i] == 'Y') places[2].push_back(i);
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0] = 0;
    for(int i = 0; i <= places[0].size(); i++){
        int u = i%2, v = (u^1);
        memset(dp[v], 0x3f, sizeof(dp[v]));
        for(int j = 0; j <= places[1].size() && i+j <= n; j++){
            for(int k = 0; k <= places[2].size() && i+j+k <= n; k++){
                for(int b = 0; b <= 2; b++){
                    int state = b, p = i+j+k;
                    if(i+j+k == 0) state = -1;
                    if(state != 0 && i < places[0].size()){
                        chmin(dp[v][j][k][0], dp[u][j][k][b] + abs(p-places[0][i]));
                    }
                    if(state != 1 && j < places[1].size()){
                        chmin(dp[u][j+1][k][1], dp[u][j][k][b] + abs(p-places[1][j]));
                    }
                    if(state != 2 && k < places[2].size()){
                        chmin(dp[u][j][k+1][2], dp[u][j][k][b] + abs(p-places[2][k]));
                    }
                }
            }
        }
    }
    long long ans = lim;
    for(int i = 0; i <= 2; i++) ans = min(ans, dp[places[0].size()%2][places[1].size()][places[2].size()][i]);
    if(ans < lim) cout<<ans/2;
    else cout<<-1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...