oj.uz

Submission #156514

# Submission time Handle Problem Language Result Execution time Memory
156514 2019-10-06T09:35:34 Z vex Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 124 ms 163100 KB 
///10:32
///10:55
///-10min
///
#include<bits/stdc++.h>
#define INF 100000000
#define maxn 405
using namespace std;

map<char,int>br;
int n;
string s;
int dp[maxn][maxn][maxn][3];
int col[maxn][3];
int tot[3];
int num[maxn][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    br['R']=0;
    br['G']=1;
    br['Y']=2;

    cin>>n;
    cin>>s;

    tot[0]=tot[1]=tot[2]=0;
    for(int i=0;i<n;i++)
    {
        int boja=br[s[i]];
        //cout<<boja<<" ";
        tot[boja]++;
        col[tot[boja]][boja]=i;

        if(i==0)
        {
            for(int j=0;j<=2;j++)
            {
                num[i][j]=0;
            }
        }
        else
        {
            for(int j=0;j<=2;j++)
            {
                num[i][j]=num[i-1][j];
            }
        }
        num[i][boja]++;
    }
    /*cout<<endl;

    for(int i=0;i<=2;i++)
    {
        cout<<tot[i]<<"  ";
        for(int j=1;j<=tot[i];j++)
        {
            cout<<col[j][i]<<" ";
        }
        cout<<endl;
    }*/



    int red[3];
    for(red[0]=0;red[0]<=tot[0];red[0]++)
    {
        for(red[1]=0;red[1]<=tot[1];red[1]++)
        {
            for(red[2]=0;red[2]<=tot[2];red[2]++)
            {
                for(int i=0;i<=2;i++)
                {
                    dp[ red[0] ][ red[1] ][ red[2] ][i]=INF;
                    if(red[i]==0)continue;

                    int tre[3];
                    for(int j=0;j<=2;j++)
                    {
                        tre[j]=red[j];
                    }
                    tre[i]--;


                    int poz=red[0]+red[1]+red[2]-1;
                    int left_ok=0;
                    for(int j=0;j<=2;j++)
                    {
                        int broj=0;
                        if(poz!=0)
                        {
                            broj=num[poz-1][j];
                        }
                        left_ok+=min(tre[j],broj);
                    }


                    int dod= (col[red[i]][i]+poz) - 2*left_ok;
                    int ost1=(i+1)%3;
                    int ost2=(i+2)%3;
                    if(poz==0)
                    {
                        dp[ red[0] ][ red[1] ][ red[2] ][i]=dod;
                        continue;
                    }


                    dp[ red[0] ][ red[1] ][ red[2] ][i]=min(dp[ red[0] ][ red[1] ][ red[2] ][i], dp[ tre[0] ][ tre[1] ][ tre[2] ][ost1] + dod);
                    dp[ red[0] ][ red[1] ][ red[2] ][i]=min(dp[ red[0] ][ red[1] ][ red[2] ][i], dp[ tre[0] ][ tre[1] ][ tre[2] ][ost2] + dod);
                }
            }
        }
    }

    int sol=INF;
    for(int i=0;i<=2;i++)
    {
        sol=min(sol,dp[ tot[0] ][ tot[1] ][ tot[2] ][i]);
    }

    if(sol>=INF)cout<<"-1"<<endl;
    else
    {
        sol/=2;
        cout<<sol<<endl;
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 3 ms 632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 3 ms 632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 123 ms 162936 KB Output is correct
3 Correct 123 ms 162256 KB Output is correct
4 Correct 124 ms 163100 KB Output is correct
5 Correct 121 ms 162936 KB Output is correct
6 Correct 121 ms 163064 KB Output is correct
7 Correct 122 ms 162168 KB Output is correct
8 Correct 121 ms 162200 KB Output is correct
9 Correct 122 ms 161400 KB Output is correct
10 Correct 123 ms 163024 KB Output is correct
11 Correct 121 ms 162936 KB Output is correct
12 Correct 35 ms 44092 KB Output is correct
13 Correct 59 ms 77176 KB Output is correct
14 Correct 84 ms 111472 KB Output is correct
15 Incorrect 122 ms 162912 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Incorrect 3 ms 632 KB Output isn't correct
11 Halted 0 ms 0 KB -