oj.uz

Submission #411059

# Submission time Handle Problem Language Result Execution time Memory
411059 2021-05-24T08:32:23 Z pliam Miners (IOI07_miners) C++14
100 / 100
 234 ms 356 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9

int dp[4][4][2][3][3][3][3];//dp[k1][k2][i%2][a1][b1][a2][b2]
int N;

int win(int a){
    return 1;
}
int win(int a,int b){
    if(a==b){
        return 1;
    }else{
        return 2;
    }
}
int win(int a,int b,int c){
    if(a==b&&b==c){
        return 1;
    }else if(a!=b&&b!=c&&a!=c){
        return 3;
    }else{
        return 2;
    }
}

int main(){
    for(int k1=0;k1<=3;k1++){
        for(int k2=0;k2<=3;k2++){
            for(int i=0;i<=1;i++){
                for(int a1=0;a1<=2;a1++){
                    for(int b1=0;b1<=2;b1++){
                        for(int a2=0;a2<=2;a2++){
                            for(int b2=0;b2<=2;b2++){
                                dp[k1][k2][i][a1][b1][a2][b2]=-INF;
                            }
                        }
                    }
                }
            }
        }
    }
    dp[0][0][0][0][0][0][0]=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        char temp;
        int d;
        scanf(" %c",&temp);
        switch(temp){
            case 'M':
                d=0;
                break;
            case 'F':
                d=1;
                break;
            case 'B':
                d=2;
                break;
        }
        //k1=1
        for(int k=0;k<=3;k++){
            for(int a=0;a<=2;a++){
                for(int b=0;b<=2;b++){
                    dp[1][k][i%2][0][d][a][b]=max(dp[1][k][i%2][0][d][a][b],dp[0][k][(i-1)%2][0][0][a][b]+win(d));
                    dp[k][1][i%2][a][b][0][d]=max(dp[k][1][i%2][a][b][0][d],dp[k][0][(i-1)%2][a][b][0][0]+win(d));
                }
            }
        }
        //k1=2
        for(int k=0;k<=3;k++){
            for(int a=0;a<=2;a++){
                for(int b=0;b<=2;b++){
                    for(int a1=0;a1<=2;a1++){
                        dp[2][k][i%2][a1][d][a][b]=max(dp[2][k][i%2][a1][d][a][b],dp[1][k][(i-1)%2][0][a1][a][b]+win(a1,d));
                        dp[k][2][i%2][a][b][a1][d]=max(dp[k][2][i%2][a][b][a1][d],dp[k][1][(i-1)%2][a][b][0][a1]+win(a1,d));
                    }
                }
            }
        }
        //k1=3
        for(int k=0;k<=3;k++){
            for(int a=0;a<=2;a++){
                for(int b=0;b<=2;b++){
                    for(int a1=0;a1<=2;a1++){
                        for(int a2=0;a2<=2;a2++){
                            dp[3][k][i%2][a2][d][a][b]=max({dp[2][k][(i-1)%2][a1][a2][a][b]+win(a1,a2,d),dp[3][k][(i-1)%2][a1][a2][a][b]+win(a1,a2,d),dp[3][k][i%2][a2][d][a][b]});
                            dp[k][3][i%2][a][b][a2][d]=max({dp[k][2][(i-1)%2][a][b][a1][a2]+win(a1,a2,d),dp[k][3][(i-1)%2][a][b][a1][a2]+win(a1,a2,d),dp[k][3][i%2][a][b][a2][d]});
                        }
                    }
                }
            }
        }
    }
    int ans=-INF;
    for(int k1=0;k1<=3;k1++){
        for(int k2=0;k2<=3;k2++){
            for(int a1=0;a1<=2;a1++){
                for(int b1=0;b1<=2;b1++){
                    for(int a2=0;a2<=2;a2++){
                        for(int b2=0;b2<=2;b2++){
                            ans=max(ans,dp[k1][k2][N%2][a1][b1][a2][b2]);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
miners.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf(" %c",&temp);
      |         ~~~~~^~~~~~~~~~~~~
miners.cpp:19:15: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |     if(a==b&&b==c){
      |              ~^~~
miners.cpp:48:13: note: 'd' was declared here
   48 |         int d;
      |             ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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