Submission #1066846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066846		stdfloat	Miners (IOI07_miners)	C++17	100 / 100	792 ms	441172 KiB

miners

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n;

string s;

vector<vector<vector<vector<vector<int>>>>> dp;

int g(char c) {
    return (c == 'A' ? 0 : (c == 'M' ? 1 : 2 + (c == 'B')));
}

int f(int x, char pa1, char pa2, char pb1, char pb2)
{
    if (x == n)
        return 0;

    int& res = dp[x][g(pa1)][g(pa2)][g(pb1)][g(pb2)];
    if (res != -1)
        return res;

    int a = (pa2 == 'A' || (pa1 == pa2 && pa2 == s[x]) ? 1 : (pa1 == 'A' ? 1 + (pa2 != s[x]) : (pa1 != pa2 && pa2 != s[x] && pa1 != s[x] ? 3 : 2)));
    int b = (pb2 == 'A' || (pb1 == pb2 && pb2 == s[x]) ? 1 : (pb1 == 'A' ? 1 + (pb2 != s[x]) : (pb1 != pb2 && pb2 != s[x] && pb1 != s[x] ? 3 : 2)));

    res = max(a + f(x + 1, pa2, s[x], pb1, pb2), b + f(x + 1, pa1, pa2, pb2, s[x]));

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;

    dp.assign(n, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));

    cout << f(0, 'A', 'A', 'A', 'A');
}

• 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