Submission #936944

#	Time	Username	Problem	Language	Result	Execution time	Memory
936944		Maite_Morale	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	60 / 100	13 ms	20316 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 405
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll t,n;
vll v[5];
string a;
ll dp[50][50][50][10],s[10]={0,0,0};
ll cost(vll x,ll z){
    ll r=0;//if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<"\n";
    for(int i=0;i<3;i++){
        if(i==z)continue;
        ll c=lower_bound(v[i].begin(),v[i].end(),v[z][x[z]-1])-v[i].begin();
        //if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<c<<" ";
        r+=max(0LL,c-x[i]);
    }//if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<r<<"\n";
return r;
}
int main(){
    fast_in
    cin>>n>>a;
    for(int i=0;i<n;i++){
        if(a[i]=='R')v[0].push_back(i+1);
        if(a[i]=='G')v[1].push_back(i+1);
        if(a[i]=='Y')v[2].push_back(i+1);
    }
    for(int i=0;i<=v[0].size();i++){
        for(int j=0;j<=v[1].size();j++){
            for(int k=0;k<=v[2].size();k++){
                for(int h=0;h<3;h++){
                    //cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<".\n";
                    if(i+j+k==0){
                        dp[i][j][k][h]=0;
                     //   cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<".\n";
                        continue;
                    }
                    s[h]=1;dp[i][j][k][h]=oo;
                    //cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<"☺\n";
                    if(min(i-s[0],min(j-s[1],k-s[2]))<0){
                      //  cout<<i-s[0]<<" "<<j-s[1]<<" "<<k-s[2]<<"\n";
                     //   cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"_\n";
                        s[h]=0;
                        continue;
                    }
                    for(int h1=0;h1<3;h1++){
                        if(h1==h)continue;
                      
                      //  if(dp[i-s[0]][j-s[1]][k-s[2]][h1]>=dp[i][j][k][h])continue;
                    //    cout<<i-s[0]<<" "<<j-s[1]<<" "<<k-s[2]<<":"<<h1<<" "<<dp[i-s[0]][j-s[1]][k-s[2]][h1]<<"\n";
                        ll z=dp[i][j][k][h],w=dp[i-s[0]][j-s[1]][k-s[2]][h1],w1=cost({i,j,k},h);
                       // cout<<z<<" "<<w<<"+"<<w1<<"*-*\n";
                        dp[i][j][k][h]=min(z,w+w1);//cout<<i<<" "<<j<<" "<<k<<" "<<h<<"\n";
                       // cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<"☻\n";
                     //   cout<<dp[i][j][k][h]/*<<"+"<<cost({i,j,k},h)*/<<" o-o\n";
                    }
                  //  cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"\n";
                    s[h]=0;
                }
            }
        }
    }
    sort(dp[v[0].size()][v[1].size()][v[2].size()],dp[v[0].size()][v[1].size()][v[2].size()]+3);
    if(dp[v[0].size()][v[1].size()][v[2].size()][0]==oo)dp[v[0].size()][v[1].size()][v[2].size()][0]=-1;
    cout<<dp[v[0].size()][v[1].size()][v[2].size()][0];
return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<=v[0].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j=0;j<=v[1].size();j++){
      |                     ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int k=0;k<=v[2].size();k++){
      |                         ~^~~~~~~~~~~~~

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