oj.uz

Submission #767961

# Submission time Handle Problem Language Result Execution time Memory
767961 2023-06-27T10:11:40 Z benjaminkleyn Miners (IOI07_miners) C++17
92 / 100
 243 ms 210468 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];
    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.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
0 / 8.0

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