Submission #1113616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113616		Dan4Life	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	360 ms	382024 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
 
const int N = (int)4e2+2;
const int INF = 0x3f3f3f3f;
 
vector<int> v[3];
int dp[N][3][N/2][N];
int n, cnt[3], chk[3][3][N];

int num(int cnt0, int cnt1, int cnt2, int f0, int f1, int f2){
    return max(0,cnt1-chk[f0][f1][cnt0])+max(0,cnt2-chk[f0][f2][cnt0]);
}
 
void swp(int i, int j){ swap(cnt[i],cnt[j]); swap(v[i],v[j]); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    string s; cin >> n >> s;
    for(int i = 0; i < n; i++){
        char u = s[i];
        if(u=='R') s[i]=0;
        else if(u=='G') s[i]=1;
        else s[i]=2;
        cnt[s[i]]++; v[s[i]].push_back(i+1);
    }
    if(cnt[0]>cnt[1])swp(0,1);
    if(cnt[1]>cnt[2])swp(1,2);
    if(cnt[0]>cnt[1])swp(0,1);
    memset(dp,INF,sizeof(dp));
    for(int i : {0,1,2}) dp[0][i][0][0]=0;
    for(int f0 = 0; f0 < 3; f0++){
        for(int f1 = 0; f1 < 3; f1++){
            int j = 0;
            for(int cnt0 = 1; cnt0 <= cnt[f0] and f0!=f1; cnt0++){
                while(j<cnt[f1] and v[f1][j]<v[f0][cnt0-1]) j++;
                chk[f0][f1][cnt0] = j;
            }
        }
    }
    int ans = INF;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            for(int m = 0; m < 3; m++){
                for(int k = 0; k <= min(i,cnt[0]) and m!=j; k++){
                    for(int l = 0; l <= min(i,cnt[1]); l++){
                        int o = i-k-l; if(o>i or o>cnt[2]) continue;
                        if(k and j==0){
                            int f0 = v[0][k-1]+num(k,l,o,0,1,2);
                            if(f0>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k-1][l]+f0-i);
                        }
                        if(l and j==1){
                            int f1 = v[1][l-1]+num(l,k,o,1,0,2);
                            if(f1>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l-1]+f1-i);
                        }
                        if(o and j==2){
                            int f2 = v[2][o-1]+num(o,k,l,2,0,1);
                            if(f2>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l]+f2-i);
                        }
                    }
                }
            }
        }
    }
    for(int j = 0; j < 3; j++)
        for(int k = 0; k <= cnt[0]; k++)
            for(int l = 0; l <= cnt[1]; l++)
                ans = min(ans, dp[n][j][k][l]);
    if(ans>=INF) ans=-1;
    cout << ans << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:25:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |         cnt[s[i]]++; v[s[i]].push_back(i+1);
      |                 ^
joi2019_ho_t3.cpp:25:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |         cnt[s[i]]++; v[s[i]].push_back(i+1);
      |                            ^

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