Submission #577933

#	Time	Username	Problem	Language	Result	Execution time	Memory
577933		MohamedFaresNebili	Miners (IOI07_miners)	C++14	100 / 100	429 ms	1020 KiB

miners

#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()

        int n, arr[2*100005]; string s; map<char, int> m;
        ll dp[2][4][4][4][4];
        int solve(int i, int j, int k) {
            int res = 0;
            for(int l = 1; l <= 3; l++)
                if(l == i || l == j || l == k) res++;
            return res;
        }

        int32_t main()
        {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> s; m['M'] = 1, m['B'] = 2, m['F'] = 3;
            for(int l = 0; l < n; l++) arr[l + 1] = m[s[l]];
            int a = 0, b = 1;
            for(int l = n; l > 0; l--) {
                swap(a, b);
                for(int u0 = 0; u0 < 4; u0++)
                    for(int u = 0; u < 4; u++)
                        for(int v0 = 0; v0 < 4; v0++)
                            for(int v = 0; v < 4; v++)
                                dp[a][u0][u][v0][v] = max(dp[b][u][arr[l]][v0][v] + solve(u0, u, arr[l]),
                                                          dp[b][u0][u][v][arr[l]] + solve(v0, v, arr[l]));
            }
            cout << dp[a][0][0][0][0] << "\n";
            return 0;
        }

• 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