Submission #477087

#	Time	Username	Problem	Language	Result	Execution time	Memory
477087		SlavicG	Miners (IOI07_miners)	C++17	100 / 100	195 ms	608 KiB

miners

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 10;
int dp[4][4][4][4];
int prev_dp[4][4][4][4];

void solve()
{  
    forn(a,4)forn(b,4)forn(c,4)forn(d,4)dp[a][b][c][d] = prev_dp[a][b][c][d] = -100000;
    int n;
    string s;
    cin >> n >> s;

    prev_dp[0][0][0][0] = 0;
    for(int i = 1;i <= n;++i){
        int x;
        if(s[i - 1] == 'M')x = 1;
        else if(s[i - 1] == 'B')x = 2;
        else x = 3;
        for(int a = 0;a < 4;++a){
            for(int b = 0;b < 4;++b){
                for(int c = 0;c < 4;++c){
                    for(int d = 0;d < 4;++d){
                        int add = 1;
                        if((x != a && a) && (x != b && b) && (a != b && a && b))add = 3;
                        else if((x != a && a) || (x != b && b) || (a != b && a && b))add = 2;
                        dp[x][a][c][d] = max(dp[x][a][c][d], prev_dp[a][b][c][d] + add);

                        add = 1;
                        if((x != c && c) && (x != d && d) && (c != d && c && d))add = 3;
                        else if((x != c && c) || (x != d && d) || (c != d && c && d))add = 2;
                        dp[a][b][x][c] = max(dp[a][b][x][c], prev_dp[a][b][c][d] + add);
                    }
                }
            }
        }

        for(int a = 0;a < 4;++a){
            for(int b = 0;b < 4;++b){
                for(int c = 0;c < 4;++c){
                    for(int d = 0;d < 4;++d){
                        prev_dp[a][b][c][d] = dp[a][b][c][d];
                        dp[a][b][c][d] = -100000;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int a = 0;a < 4;++a){
        for(int b = 0;b < 4;++b){
            for(int c = 0;c < 4;++c){
                for(int d = 0;d < 4;++d){
                    ans = max(ans, prev_dp[a][b][c][d]);
                }
            }
        }
    }
    cout << ans << "\n";
}  
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

• 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