Submission #544865

#	Time	Username	Problem	Language	Result	Execution time	Memory
544865		Deepesson	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	24 ms	4436 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define MAX 305
///Uma dp meio complicadinha
///A ideia eh a seguinte:
///1-> Quantos valores azuis restam
///2-> Quantos valores vermelhos restam
///3-> Quantos valores verdes restam
///4-> (Para remover) coordenada atual
///Por enquanto sera O(N^4), mas poderemos otimizar depois
bool existe[4][MAX][MAX][MAX][4];
int tab[3][MAX][MAX][MAX][4];
std::vector<int> cords[3];
int N;
int array[MAX]={};
int getval(char ch){
    if(ch=='R')return 0;else if(ch=='G')return 1;return 2;
}
int proximo(int red,int blue,int green){
    int min=N;
    if(red!=cords[0].size())min=std::min(min,cords[0][red]);
    if(green!=cords[1].size())min=std::min(min,cords[1][green]);
    if(blue!=cords[2].size())min=std::min(min,cords[2][blue]);
    return min;
}
int dp(int val,int red,int blue,int green,int last){
    if(red+blue+green==N)return 0;
    int pos=0;
    {
        int arr[]={red,green,blue};
        pos=cords[val][arr[val]];
    }
    if(existe[val][red][blue][green][last])return tab[val][red][blue][green][last];
    existe[val][red][blue][green][last]=true;
    ///Prossegue com o valor
    int ans=1e9;
    if(array[pos]!=last){
        switch(array[pos]){
            case 0:
            ans=dp(array[proximo(red+1,blue,green)],red+1,blue,green,array[pos]);break;
            case 1:
            ans=dp(array[proximo(red,blue,green+1)],red,blue,green+1,array[pos]);break;
            case 2:
            ans=dp(array[proximo(red,blue+1,green)],red,blue+1,green,array[pos]);break;
        }
    }
    ///O valor da distancia estah INCORRETO, como melhorar a conta?
    ///Faz a troca magica
    if(last!=0&&red!=cords[0].size()&&array[pos]!=0){
        int truecusto=0;
        int destino = cords[0][red];
        for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
        for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
        for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
        ans=std::min(ans,cords[0][red]-pos-truecusto + (dp(val,red+1,blue,green,0)));
    }
    if(last!=1&&green!=cords[1].size()&&array[pos]!=1){
        int truecusto=0;
        int destino = cords[1][green];
        for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
        for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
        for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
        ans=std::min(ans,cords[1][green]-pos-truecusto + (dp(val,red,blue,green+1,1)));
    }
    if(last!=2&&blue!=cords[2].size()&&array[pos]!=2){
        int truecusto=0;
        int destino = cords[2][blue];
        for(int i=0;i!=red;++i)if(cords[0][i]>=pos&&cords[0][i]<=destino)++truecusto;
        for(int i=0;i!=green;++i)if(cords[1][i]>=pos&&cords[1][i]<=destino)++truecusto;
        for(int i=0;i!=blue;++i)if(cords[2][i]>=pos&&cords[2][i]<=destino)++truecusto;
        ans=std::min(ans,cords[2][blue]-pos-truecusto + (dp(val,red,blue+1,green,2)));
    }
    return tab[val][red][blue][green][last]=ans;
}
int main()
{
    std::cin>>N;
    std::string s;
    std::cin>>s;
    for(int i=0;i!=s.size();++i){
        int u = getval(s[i]);
        cords[u].push_back(i);
        array[i]=u;
    }
    int ans=dp(array[0],0,0,0,3);
    if(ans==1e9)ans=-1;
    std::cout<<ans<<"\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int proximo(int, int, int)':
joi2019_ho_t3.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if(red!=cords[0].size())min=std::min(min,cords[0][red]);
      |        ~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:21:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(green!=cords[1].size())min=std::min(min,cords[1][green]);
      |        ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(blue!=cords[2].size())min=std::min(min,cords[2][blue]);
      |        ~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int dp(int, int, int, int, int)':
joi2019_ho_t3.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if(last!=0&&red!=cords[0].size()&&array[pos]!=0){
      |                 ~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if(last!=1&&green!=cords[1].size()&&array[pos]!=1){
      |                 ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(last!=2&&blue!=cords[2].size()&&array[pos]!=2){
      |                 ~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i!=s.size();++i){
      |                 ~^~~~~~~~~~

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