oj.uz

Submission #216128

# Submission time Handle Problem Language Result Execution time Memory
216128 2020-03-26T18:25:43 Z anmichi Miners (IOI07_miners) C++17
100 / 100
 234 ms 1024 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000;
int main(){
    int n,a[100010],dp[2][4][4][4][4];
    string s;
    cin>>n>>s;
    rep(i,2){
        rep(c,4){
            rep(d,4){
                rep(e,4){
                    rep(f,4){
                        dp[i][c][d][e][f]=-INF;
                    }
                }
            }
        }
    }
    dp[0][3][3][3][3]=0;
    rep(i,n){
        if(s[i]=='M')a[i]=0;
        if(s[i]=='F')a[i]=1;
        if(s[i]=='B')a[i]=2;
    }
    rep(i,n){
        rep(c,4){
            rep(d,4){
                if(c==3&&d!=3)continue;
                rep(e,4){
                    rep(f,4){
                        int x[4]={0,0,0,0},y[4]={0,0,0,0};
                        x[c]++,x[d]++,x[a[i]]++;
                        y[e]++,y[f]++,y[a[i]]++;
                        int X=0,Y=0;
                        rep(i,3){
                            X+=(bool)x[i];
                            Y+=(bool)y[i];
                        }
                        chmax(dp[(i+1)%2][a[i]][c][e][f],dp[i%2][c][d][e][f]+X);
                        chmax(dp[(i+1)%2][c][d][a[i]][e],dp[i%2][c][d][e][f]+Y);
                    }
                }
            }
        }
    }
    int ans=0;
    rep(c,4){
        rep(d,4){
            if(c==3&&d!=3)continue;
            rep(e,4){
                rep(f,4){
                    if(e==3&&f!=3)continue;
                    chmax(ans,dp[n%2][c][d][e][f]);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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