Submission #1016202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016202		snpmrnhlol	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	231 ms	134736 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
const int N = 400;
const int inf = 2e9;
char v[N];
int f[3];
vector<vector<vector<vector<int>>>> dp;
vector <int> pos[3];
int v2[N][3];
int get(int i,int j,int l,int id){
    int ans = 0;
    int pos2;
    if(id == 0){
        pos2 = pos[id][i];
    }else if(id == 1){
        pos2 = pos[id][j];
    }else{
        pos2 = pos[id][l];
    }
    if(id != 0){
        ans+=max(i - v2[pos2][0],0);
    }
    if(id != 1){
        ans+=max(j - v2[pos2][1],0);
    }
    if(id != 2){
        ans+=max(l - v2[pos2][2],0);
    }
    //cout<<i<<' '<<j<<' '<<l<<' '<<id<<' '<<ans<<'\n';
    return ans;
}
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
        v[i] = (v[i] == 'R'?0:(v[i] == 'G'?1:2));
        f[v[i]]++;
        pos[v[i]].push_back(i);
        for(int j = 0;j < 3;j++){
            v2[i][j] = (int)pos[j].size();
        }
    }
    dp.assign(f[0] + 1,vector<vector<vector<int>>>(f[1] + 1,vector<vector<int>>(f[2] + 1,vector<int>(3,inf))));
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    dp[0][0][0][0] = 0;
    for(int i = 0;i <= f[0];i++){
        for(int j = 0;j <= f[1];j++){
            for(int l = 0;l <= f[2];l++){
                for(int k = 0;k < 3;k++){
                    if(i != f[0] && k != 0){
                        dp[i + 1][j][l][0] = min(dp[i + 1][j][l][0],dp[i][j][l][k] + get(i,j,l,0));
                    }
                    if(j != f[1] && k != 1){
                        dp[i][j + 1][l][1] = min(dp[i][j + 1][l][1],dp[i][j][l][k] + get(i,j,l,1));
                    }
                    if(l != f[2] && k != 2){
                        dp[i][j][l + 1][2] = min(dp[i][j][l + 1][2],dp[i][j][l][k] + get(i,j,l,2));
                    }
                }
            }
        }
    }
    int ans = min({dp[f[0]][f[1]][f[2]][0],dp[f[0]][f[1]][f[2]][1],dp[f[0]][f[1]][f[2]][2]});
    if(ans == inf)ans = -1;
    cout<<ans;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:38:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |         f[v[i]]++;
      |           ~~~^
joi2019_ho_t3.cpp:39:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |         pos[v[i]].push_back(i);
      |             ~~~^

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