Submission #767961

#	Time	Username	Problem	Language	Result	Execution time	Memory
767961		benjaminkleyn	Miners (IOI07_miners)	C++17	92 / 100	243 ms	210468 KiB

miners

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

int N, v[100001];
ll memo[100001][4][4][4][4];

int score(int a, int b, int c)
{
    if (b == 3) b = c;
    if (a == 3) a = b;
    if (a == b && b == c) return 1;
    if (a == b || b == c || c == a) return 2;
    return 3;
}

ll dp(int i, int a = 3, int b = 3, int c = 3, int d = 3)
{
    if (memo[i][a][b][c][d] != -1)
        return memo[i][a][b][c][d];
    if (i > N) return 0;
    return memo[i][a][b][c][d] = max(dp(i + 1, b, v[i], c, d) + score(a, b, v[i]), dp(i + 1, a, b, d, v[i]) + score(c, d, v[i]));
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        char x;
        cin >> x;
        v[i] = (x == 'F') + 2 * (x == 'B');
    }

    for (int i = 0; i <= N; i++)
        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++)
                        memo[i][a][b][c][d] = -1;

    cout << dp(1) << '\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: 0 / 8