oj.uz

Submission #577933

# Submission time Handle Problem Language Result Execution time Memory
577933 2022-06-15T13:33:24 Z MohamedFaresNebili Miners (IOI07_miners) C++14
100 / 100
 429 ms 1020 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 496 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 876 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 1020 KB Output is correct