Submission #1157538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157538		dnnnda	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	58 ms	4168 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

int col[405], pre[3][405], last[405][405][3], dp[405][405][3];
vector<int> v[3];

int cal(array<int,4> arr){
    int ret=0, pos=v[arr[3]][arr[arr[3]]-1];
    //cout << pos << '\n';
    for(int i=0 ; i<3 ; i++){
        ret+=max(pre[i][pos]-arr[i],0);
        //cout << ret << '\n';
    }
    //cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << ' ' << arr[3] << " = " << ret << '\n';
    //return ret+pos-(arr[0]+arr[1]+arr[2]);
    return ret;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(pre,0,sizeof pre);
    memset(last,0x3f,sizeof last);
    memset(dp,0x3f,sizeof dp);
    int n; cin >> n;
    for(int i=1 ; i<=n ; i++){
        char c; cin >> c;
        if(c=='R') col[i]=0;
        if(c=='G') col[i]=1;
        if(c=='Y') col[i]=2;
        v[col[i]].push_back(i);
        pre[col[i]][i]++;
    }
    for(int i=1 ; i<=n ; i++){
        for(int j=0 ; j<3 ; j++) pre[j][i]+=pre[j][i-1];
    }
    //for(int i=1 ; i<=n ; i++) for(int j=0 ; j<3 ; j++) cout << j << ' ' << i << ' ' << pre[j][i] << '\n';
    last[0][0][0]=last[0][0][1]=last[0][0][2]=0;
    for(int r=1 ; r<=n ; r++){
        for(int i=0 ; i<=n ; i++) for(int j=0 ; j<=n ; j++) for(int u=0 ; u<3 ; u++)
            dp[i][j][u]=inf;
        for(int i=0 ; i<=r ; i++) for(int j=0 ; i+j<=r ; j++){
            int k=r-i-j;
            if(i>v[0].size()||j>v[1].size()||k>v[2].size()) continue;
            if(i>0) dp[i][j][0]=min(last[i-1][j][1],last[i-1][j][2])+cal({i,j,k,0});
            if(j>0) dp[i][j][1]=min(last[i][j-1][0],last[i][j-1][2])+cal({i,j,k,1});
            if(k>0) dp[i][j][2]=min(last[i][j][0],last[i][j][1])+cal({i,j,k,2});
            //for(int u=0 ; u<3 ; u++) cout << i << ' ' << j << ' ' << k << ' ' << u << " = " << dp[i][j][u] << '\n';
        }
        for(int i=0 ; i<=r ; i++) for(int j=0 ; i+j<=r ; j++){
            swap(last[i][j][0],dp[i][j][0]);
            swap(last[i][j][1],dp[i][j][1]);
            swap(last[i][j][2],dp[i][j][2]);
        }
    }
    int i=v[0].size(), j=v[1].size();
    if(min({last[i][j][0],last[i][j][1],last[i][j][2]})==inf) cout << "-1\n";
    else cout << min({last[i][j][0],last[i][j][1],last[i][j][2]}) << '\n';

    return 0;
}

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