oj.uz

Submission #54542

# Submission time Handle Problem Language Result Execution time Memory
54542 2018-07-04T04:11:19 Z 노영훈(#1490) Miners (IOI07_miners) C++11
100 / 100
 208 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n;
char S[MX];

int D[2][20][20];

int f(char x){
    if(x=='M') return 1;
    if(x=='B') return 2;
    if(x=='F') return 3;
    return 0;
}

int g(int a, int x){
    int y=a%4, z=a/4;
    int cnt=0;
    if(x>0) cnt++;
    if(y>0 && x!=y) cnt++;
    if(z>0 && x!=z && y!=z) cnt++;
    return cnt;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    cin>>(S+1);
    for(int s=0; s<16; s++)
        for(int t=0; t<16; t++)
            D[0][s][t]=-inf;
    D[0][0][0]=0;
    for(int i=0; i<n; i++){
        for(int s=0; s<16; s++)
            for(int t=0; t<16; t++)
                D[(i&1)^1][s][t]=-inf;
        int u=f(S[i+1]);
        for(int s=0; s<16; s++){
            for(int t=0; t<16; t++){
                {
                    int &d=D[(i&1)^1][(s%4)*4+u][t];
                    int x=g(s, u);
                    d=max(d, D[i&1][s][t]+x);
                }
                {
                    int &d=D[(i&1)^1][s][(t%4)*4+u];
                    int x=g(t, u);
                    d=max(d, D[i&1][s][t]+x);
                }
            }
        }
    }
    int ans=0;
    for(int s=0; s<16; s++)
        for(int t=0; t<16; t++)
            ans=max(ans, D[n&1][s][t]);
    cout<<ans;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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