Submission #670503

#	Time	Username	Problem	Language	Result	Execution time	Memory
670503		berr	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	433 ms	767972 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;    
int a[405][3][405][405]; 
array<int, 3> p[405];


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> b[3];

    string s; cin>>s;


    for(int l=0; l<3; l++) b[l].push_back(0);

    for(int i = 1; i <=n; i++){
        p[i]=p[i-1];
        if(s[i-1]=='R') b[0].push_back(i), p[i][0]++;
        if(s[i-1]=='Y') b[1].push_back(i), p[i][1]++;
        if(s[i-1]=='G') b[2].push_back(i), p[i][2]++;


    }


    for(int i=1; i<=n; i++){
        for(int l=0; l<3; l++){
            for(int j=0; j<=n; j++)
            {
                for(int f=0; f<=n; f++)
                {
                    a[i][l][j][f]=1e9;
                }
            }
        }
    }


    for(int l=0; l<3; l++) b[l].push_back(n+1);
    int ans=1e9;

    for(int i=1; i<=n; i++){
        for(int l=0; l<=i&&l<b[0].size()-1; l++){
            for(int j=0; j+l<=i&&j<b[1].size()-1; j++){
                int k=i-(j+l);
                if(k<b[2].size()-1)
                for(int t=0; t<3; t++){
                    int dist=0;

                    int f=0;
                    if(t==0) f=l;
                    else if(t==1) f=j;
                    else f=k;

                    dist+=max(0, p[b[t][f]][0]-l);
                    dist+=max(0, p[b[t][f]][1]-j);
                    dist+=max(0, p[b[t][f]][2]-k);


                    for(int g=0; g<3&&f; g++){
                        if(t==0&&g!=t&&(l>0||i==1))
                        a[i][t][l][j]=min(a[i-1][g][max(0, l-1)][j]+dist, a[i][t][l][j]);
                        if(t==1&&g!=t&&(j>0||i==1))
                        a[i][t][l][j]=min(a[i-1][g][l][max(0, j-1)]+dist, a[i][t][l][j]);
                        if(t==2&&g!=t&&(k>0||i==1))
                        a[i][t][l][j]=min(a[i-1][g][l][j]+dist, a[i][t][l][j]);
                    
                    }

                    if(i==n) ans=min(ans, a[i][t][l][j]);
                }


            }
    
        }
    }



    if(ans>=1e9) cout<<-1;
    else cout<<ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int l=0; l<=i&&l<b[0].size()-1; l++){
      |                            ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:46:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int j=0; j+l<=i&&j<b[1].size()-1; j++){
      |                                  ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 if(k<b[2].size()-1)
      |                    ~^~~~~~~~~~~~~~

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