제출 #1344552

#제출 시각아이디문제언어결과실행 시간메모리
1344552khanhphucscratchGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
48 ms8144 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];
vector<int> minplace[3][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);
    }
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++) if(i != j){
            minplace[i][j].resize(places[i].size());
            for(int k = 0; k < places[i].size(); k++){
                minplace[i][j][k] = -1;
                for(int l = 0; l < places[j].size(); l++) if(places[i][k] > places[j][l]) minplace[i][j][k] = l;
            }
        }
    }
    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()){
                        int np = places[0][i] + max(j-1 - minplace[0][1][i], 0) + max(k-1 - minplace[0][2][i], 0);
                        chmin(dp[v][j][k][0], dp[u][j][k][b] + abs(p-np));
                    }
                    if(state != 1 && j < places[1].size()){
                        int np = places[1][j] + max(i-1 - minplace[1][0][j], 0) + max(k-1 - minplace[1][2][j], 0);
                        chmin(dp[u][j+1][k][1], dp[u][j][k][b] + abs(p-np));
                    }
                    if(state != 2 && k < places[2].size()){
                        int np = places[2][k] + max(i-1 - minplace[2][0][k], 0) + max(j-1 - minplace[2][1][k], 0);
                        chmin(dp[u][j][k+1][2], dp[u][j][k][b] + abs(p-np));
                    }
                    //if(dp[u][j][k][b] < lim) cerr<<"A"<<i<<" "<<j<<" "<<k<<" "<<b<<" "<<dp[u][j][k][b]<<endl;
                }
            }
        }
    }
    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;
    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...