oj.uz

Submission #730681

# Submission time Handle Problem Language Result Execution time Memory
730681 2023-04-26T09:10:26 Z lucri Miners (IOI07_miners) C++17
100 / 100
 305 ms 102064 KB 
#include <iostream>
using namespace std;
int n,pd[100010][260],ans;
char a[100010];
int codifica(char a)
{
    if(a=='M')
        return 1;
    if(a=='B')
        return 2;
    return 3;
}
void adauga(int poz,int a,int b,int c,int d,int ad)
{
    int valcal;
    if(a&&b==0||c&&d==0||pd[poz-1][a*4*4*4+b*4*4+c*4+d]==-2000000000)
        return;
    if(a&&b)
    {
        valcal=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+3;
        if(a==b||a==ad)
            --valcal;
        if(b==ad)
            --valcal;
        if(valcal>pd[poz][b*4*4*4+ad*4*4+c*4+d])
            pd[poz][b*4*4*4+ad*4*4+c*4+d]=valcal;
    }
    else if(b)
    {
        valcal=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+2;
        if(b==ad)
            --valcal;
        if(valcal>pd[poz][b*4*4*4+ad*4*4+c*4+d])
            pd[poz][b*4*4*4+ad*4*4+c*4+d]=valcal;
    }
    else if(pd[poz-1][a*4*4*4+b*4*4+c*4+d]+1>pd[poz][b*4*4*4+ad*4*4+c*4+d])
        pd[poz][b*4*4*4+ad*4*4+c*4+d]=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+1;
    if(c&&d)
    {
        valcal=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+3;
        if(c==d||c==ad)
            --valcal;
        if(d==ad)
            --valcal;
        if(valcal>pd[poz][a*4*4*4+b*4*4+d*4+ad])
            pd[poz][a*4*4*4+b*4*4+d*4+ad]=valcal;
    }
    else if(d)
    {
        valcal=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+2;
        if(d==ad)
            --valcal;
        if(valcal>pd[poz][a*4*4*4+b*4*4+d*4+ad])
            pd[poz][a*4*4*4+b*4*4+d*4+ad]=valcal;
    }
    else if(pd[poz-1][a*4*4*4+b*4*4+c*4+d]+1>pd[poz][a*4*4*4+b*4*4+d*4+ad])
        pd[poz][a*4*4*4+b*4*4+d*4+ad]=pd[poz-1][a*4*4*4+b*4*4+c*4+d]+1;
}
int main()
{
    cin>>n>>a+1;
    for(int i=0;i<=255;++i)
        pd[0][i]=-2000000000;
    pd[0][0]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=255;++j)
            pd[i][j]=-2000000000;
        int cod=codifica(a[i]);
        for(int a=0;a<=3;++a)
            for(int b=0;b<=3;++b)
                for(int c=0;c<=3;++c)
                    for(int d=0;d<=3;++d)
                        adauga(i,a,b,c,d,cod);
    }
    for(int i=0;i<=255;++i)
        if(pd[n][i]>ans)
            ans=pd[n][i];
    /*for(int i=0;i<256;++i)
        cout<<pd[n][i]<<'\n';*/
    cout<<ans;
    return 0;
}

Compilation message

miners.cpp: In function 'void adauga(int, int, int, int, int, int)':
miners.cpp:16:9: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   16 |     if(a&&b==0||c&&d==0||pd[poz-1][a*4*4*4+b*4*4+c*4+d]==-2000000000)
      |        ~^~~~~~
miners.cpp: In function 'int main()':
miners.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     cin>>n>>a+1;
      |             ~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5332 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10476 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 25688 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 76596 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 102064 KB Output is correct