oj.uz

Submission #767960

# Submission time Handle Problem Language Result Execution time Memory
767960 2023-06-27T10:09:10 Z benjaminkleyn Miners (IOI07_miners) C++17
92 / 100
 195 ms 212140 KB 
#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];
    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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 212140 KB Output isn't correct
2 Halted 0 ms 0 KB -