Submission #618992

#	Time	Username	Problem	Language	Result	Execution time	Memory
618992		neki	Miners (IOI07_miners)	C++14	100 / 100	428 ms	200888 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8