oj.uz

Submission #618992

# Submission time Handle Problem Language Result Execution time Memory
618992 2022-08-02T08:48:39 Z neki Miners (IOI07_miners) C++14
100 / 100
 428 ms 200888 KB 
#include <bits/stdc++.h>
#define vc vector
#define ll long long

using namespace std;



int main() {
    ll n;cin >> n;
    string s;cin >> s;
    vc<char> chs={'0', 'M', 'F', 'B'};
    auto fndind=[&](char c){
        for(ll i=0;i<4;++i) if(chs[i]==c) return i;
        assert(0);
        return -1LL;
    };
    auto get=[&](vc<ll> arr){
        ll ret=0;
        for(ll i=1;i<=3;++i){ for(auto v: arr) if(v==i){++ret;break;}}
        return ret;
    };
    ll dp[n+1][4][4][4][4];
    
    for(ll i=0;i<=n;++i) for(ll a1=0;a1<4;++a1) for(ll b1=0;b1<4;++b1) for(ll a2=0;a2<4;++a2) for(ll b2=0;b2<4;++b2) dp[i][a1][b1][a2][b2]=-1;
    dp[0][0][0][0][0]=0;
    for(ll i=1;i<=n;++i){
        ll ch=fndind(s[i-1]);
        
        for(ll a1=0;a1<4;++a1) for(ll b1=0;b1<4;++b1) for(ll a2=0;a2<4;++a2) for(ll b2=0;b2<4;++b2)if(dp[i-1][a1][b1][a2][b2]!=-1){
            dp[i][b1][ch][a2][b2]=max(dp[i][b1][ch][a2][b2], dp[i-1][a1][b1][a2][b2] + get({a1, b1, ch}));
            dp[i][a1][b1][b2][ch]=max(dp[i][a1][b1][b2][ch], dp[i-1][a1][b1][a2][b2] + get({a2, b2, ch}));
        }
    }
    ll ans=0;
    for(ll a1=0;a1<4;++a1) for(ll b1=0;b1<4;++b1) for(ll a2=0;a2<4;++a2) for(ll b2=0;b2<4;++b2)if(dp[n][a1][b1][a2][b2]!=-1) ans=max(ans, dp[n][a1][b1][a2][b2]);
    cout << ans << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 212 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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