Submission #852018

#	Time	Username	Problem	Language	Result	Execution time	Memory
852018		damwuan	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	248 ms	774228 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=400+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,a[maxn],id[maxn],dp[maxn][maxn][maxn][3],pre[maxn][3];
string s;
vector<int> L1,L2,L0;
int cost(int j0,int j1,int j2,int add)
{
    if (add==0)
    {
        return max(pre[L0[j0]][1]  - pre[L1[j1]][1],0) +
        max(pre[L0[j0]][2]  - pre[L2[j2]][2],0);
    }
    else if (add==1)
    {
        return max(pre[L1[j1]][0]  - pre[L0[j0]][0],0) +
        max(pre[L1[j1]][2]  - pre[L2[j2]][2],0);
    }
    else
    {
        return max(pre[L2[j2]][0]  - pre[L0[j0]][0],0) +
        max(pre[L2[j2]][1]  - pre[L1[j1]][1],0);
    }
}

void sol()
{
    id['R']=0;
    id['G']=1;
    id['Y']=2;
    cin >> n>> s;
    int n0=0,n1=0,n2=0;
    L1.pb(0);
    L2.pb(0);
    L0.pb(0);
    for1(i,1,n)
    {
        a[i]=id[s[i-1]];
        if(a[i]==0)
        {
            n0++;
            L0.pb(i);
        }
        if(a[i]==1)
        {
            n1++;
            L1.pb(i);
        }
        if(a[i]==2)
        {
            n2++;
            L2.pb(i);
        }
    }
    for1(j,0,2)
    {
        for1(i,1,n)
        {
            pre[i][j]=pre[i-1][j]+(a[i]==j);
        }
    }
    for1(i,0,n) for1(j0,0,n) for1(j1,0,n) for1(k,0,2) dp[i][j0][j1][k]=inf;
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    dp[0][0][0][2]=0;
    for1(i,1,n)
    {
        for1(j0,0,int(min(n0,i)))
        {
            for1(j1,0,int(min(n1,i-j0)))
            {

                int j2=i-j0-j1;
                if (j2>n2) continue;
                if (j0>0) dp[i][j0][j1][0]=min(dp[i][j0][j1][0],min(dp[i-1][j0-1][j1][1],dp[i-1][j0-1][j1][2])+cost(j0,j1,j2,0));
                if (j1>0) dp[i][j0][j1][1]=min(dp[i][j0][j1][1],min(dp[i-1][j0][j1-1][2],dp[i-1][j0][j1-1][0])+cost(j0,j1,j2,1));
                if (j2>0)
                {
                    dp[i][j0][j1][2]=min(dp[i][j0][j1][2],min(dp[i-1][j0][j1][1],dp[i-1][j0][j1][0])+cost(j0,j1,j2,2));
//                    if (i==1 && j0==0 && j1==0) cerr<< "awdawd\n";
                }
//                cerr<<i<<' ' << j0<<' '<<j1<<' '<<dp[n][n0][n1][0]<< ' '<<dp[n][n0][n1][1]<<' '<<dp[n][n0][n1][2]<<'\n';
            }
        }
    }
//    cerr<< cost(0,0,1,2)<<" wtf\n";
int ans=min(dp[n][n0][n1][0],min(dp[n][n0][n1][1],dp[n][n0][n1][2]));
    if (ans>=inf) cout << "-1";
    else cout << ans;

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 5 2 4 1
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void sol()':
joi2019_ho_t3.cpp:58:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |         a[i]=id[s[i-1]];
      |                       ^

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