oj.uz

Submission #544861

# Submission time Handle Problem Language Result Execution time Memory
544861 2022-04-02T23:06:40 Z Deepesson Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 10 ms 16084 KB 
#include <bits/stdc++.h>
#define MAX 65
///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[MAX][MAX][MAX][MAX][4];
int tab[MAX][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 dp(int pos,int red,int blue,int green,int last){
    if(pos==N)return 0;
    if(existe[pos][red][blue][green][last])return tab[pos][red][blue][green][last];
    existe[pos][red][blue][green][last]=true;
    switch(array[pos]){
        case 0:
            if(cords[0][red]!=pos)
                return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
        case 1:
            if(cords[1][green]!=pos)
                return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
        case 2:
            if(cords[2][blue]!=pos)
                return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
    }
    ///Prossegue com o valor
    int ans=1e9;
    if(array[pos]!=last){
        switch(array[pos]){
            case 0:
            ans=dp(pos+1,red+1,blue,green,array[pos]);break;
            case 1:
            ans=dp(pos+1,red,blue,green+1,array[pos]);break;
            case 2:
            ans=dp(pos+1,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()){
        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(pos,red+1,blue,green,0)));
    }
    if(last!=1&&green!=cords[1].size()){
        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(pos,red,blue,green+1,1)));
    }
    if(last!=2&&blue!=cords[2].size()){
        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(pos,red,blue+1,green,2)));
    }
    return tab[pos][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(0,0,0,0,3);
    if(ans==1e9)ans=-1;
    std::cout<<ans<<"\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int dp(int, int, int, int, int)':
joi2019_ho_t3.cpp:24:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |             if(cords[0][red]!=pos)
      |             ^~
joi2019_ho_t3.cpp:25:87: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |                 return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
      |                                                                                       ^~~~~
joi2019_ho_t3.cpp:27:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |             if(cords[1][green]!=pos)
      |             ^~
joi2019_ho_t3.cpp:28:87: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |                 return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
      |                                                                                       ^~~~~
joi2019_ho_t3.cpp:30:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |             if(cords[2][blue]!=pos)
      |             ^~
joi2019_ho_t3.cpp:31:87: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |                 return tab[pos][red][blue][green][last]=dp(pos+1,red,blue,green,last);break;
      |                                                                                       ^~~~~
joi2019_ho_t3.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(last!=0&&red!=cords[0].size()){
      |                 ~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(last!=1&&green!=cords[1].size()){
      |                 ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if(last!=2&&blue!=cords[2].size()){
      |                 ~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i!=s.size();++i){
      |                 ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 952 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 568 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 576 KB Output is correct
17 Correct 0 ms 340 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 952 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 568 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 576 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 9 ms 12920 KB Output is correct
19 Correct 8 ms 12116 KB Output is correct
20 Correct 8 ms 12792 KB Output is correct
21 Correct 8 ms 12628 KB Output is correct
22 Correct 8 ms 12884 KB Output is correct
23 Correct 8 ms 10680 KB Output is correct
24 Correct 4 ms 6228 KB Output is correct
25 Correct 1 ms 980 KB Output is correct
26 Correct 2 ms 3156 KB Output is correct
27 Correct 10 ms 15444 KB Output is correct
28 Correct 3 ms 2516 KB Output is correct
29 Correct 6 ms 6996 KB Output is correct
30 Correct 3 ms 2388 KB Output is correct
31 Correct 8 ms 12884 KB Output is correct
32 Correct 9 ms 16084 KB Output is correct
33 Correct 2 ms 3284 KB Output is correct
34 Correct 2 ms 4692 KB Output is correct
35 Correct 5 ms 8020 KB Output is correct
36 Correct 5 ms 6484 KB Output is correct
37 Correct 6 ms 6740 KB Output is correct
38 Correct 5 ms 4948 KB Output is correct
39 Correct 8 ms 9300 KB Output is correct
40 Correct 1 ms 724 KB Output is correct
41 Correct 2 ms 1876 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 6 ms 344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 952 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 568 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 576 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 9 ms 12920 KB Output is correct
19 Correct 8 ms 12116 KB Output is correct
20 Correct 8 ms 12792 KB Output is correct
21 Correct 8 ms 12628 KB Output is correct
22 Correct 8 ms 12884 KB Output is correct
23 Correct 8 ms 10680 KB Output is correct
24 Correct 4 ms 6228 KB Output is correct
25 Correct 1 ms 980 KB Output is correct
26 Correct 2 ms 3156 KB Output is correct
27 Correct 10 ms 15444 KB Output is correct
28 Correct 3 ms 2516 KB Output is correct
29 Correct 6 ms 6996 KB Output is correct
30 Correct 3 ms 2388 KB Output is correct
31 Correct 8 ms 12884 KB Output is correct
32 Correct 9 ms 16084 KB Output is correct
33 Correct 2 ms 3284 KB Output is correct
34 Correct 2 ms 4692 KB Output is correct
35 Correct 5 ms 8020 KB Output is correct
36 Correct 5 ms 6484 KB Output is correct
37 Correct 6 ms 6740 KB Output is correct
38 Correct 5 ms 4948 KB Output is correct
39 Correct 8 ms 9300 KB Output is correct
40 Correct 1 ms 724 KB Output is correct
41 Correct 2 ms 1876 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Runtime error 6 ms 344 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -