Submission #866782

#	Time	Username	Problem	Language	Result	Execution time	Memory
866782		12345678	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	35 ms	28764 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int nx=405;
int n, mp[100], qs[3][nx], r[3][nx], res=INT_MAX;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    mp['R']=0; mp['G']=1; mp['Y']=2;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<3; j++) qs[j][i]=qs[j][i-1];
        qs[mp[s[i-1]]][i]++;
        r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
    }
    int dp[qs[0][n]+1][qs[1][n]+1][qs[2][n]+1][3];
    //for (int i=1; i<=n; i++) cout<<i<<' '<<qs[0][i]<<' '<<qs[1][i]<<' '<<qs[2][i]<<'\n';
    //for (int i=1; i<=n; i++) cout<<i<<' '<<r[0][i]<<' '<<r[1][i]<<' '<<r[2][i]<<'\n';
    for (int i=0; i<=qs[0][n]; i++)
    {
        for (int j=0; j<=qs[1][n]; j++)
        {
            for (int k=0; k<=qs[2][n]; k++)
            {
                dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=1e6;
                if (i==0&&j==0&&k==0) dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=0;
                if (i>0) 
                {
                    int c=r[0][i], f1=qs[1][c], f2=qs[2][c], cst=0;
                    if (f1>j) cst+=f1-j;
                    if (f2>k) cst+=f2-k;
                    dp[i][j][k][0]=min({dp[i-1][j][k][1]+cst, dp[i-1][j][k][2]+cst, dp[i][j][k][0]});
                }
                if (j>0)
                {
                    int c=r[1][j], f1=qs[0][c], f2=qs[2][c], cst=0;
                    if (f1>i) cst+=f1-i;
                    if (f2>k) cst+=f2-k;
                    dp[i][j][k][1]=min({dp[i][j-1][k][0]+cst, dp[i][j-1][k][2]+cst, dp[i][j][k][1]});
                }
                if (k>0)
                {
                    int c=r[2][k], f1=qs[0][c], f2=qs[1][c], cst=0;
                    if (f1>i) cst+=f1-i;
                    if (f2>j) cst+=f2-j;
                    //cout<<"here"<<' '<<cst<<' '<<c<<'\n';
                    dp[i][j][k][2]=min({dp[i][j][k-1][0]+cst, dp[i][j][k-1][1]+cst, dp[i][j][k][2]});
                }
                //cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k][0]<<' '<<dp[i][j][k][1]<<' '<<dp[i][j][k][2]<<'\n';
            }
        }
    }
    for (int i=0; i<3; i++) res=min(res, dp[qs[0][n]][qs[1][n]][qs[2][n]][i]);
    if (res==1e6) cout<<-1;
    else cout<<res;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:17:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |         qs[mp[s[i-1]]][i]++;
      |                     ^
joi2019_ho_t3.cpp:18:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
      |                    ^
joi2019_ho_t3.cpp:18:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
      |                                   ^

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