oj.uz

Submission #484733

# Submission time Handle Problem Language Result Execution time Memory
484733 2021-11-05T10:34:40 Z Alexandruabcde Miners (IOI07_miners) C++14
100 / 100
 119 ms 496 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;
constexpr int MIN_INF = -1e9;

int N;
char ch[NMAX];

int dp[2][4][4][4][4];

int Value (char c) {
    if (c == 'B') return 1;

    if (c == 'F') return 2;

    return 3;
}

int FindAdd (int a, int b, int c) {
    int fr[4];
    memset(fr, 0, sizeof(fr));

    fr[a] ++;
    fr[b] ++;
    fr[c] ++;

    int val = 0;
    for (int i = 1; i <= 3; ++ i )
        val += (fr[i] != 0);

    return val;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> ch[i];
}

void Reset (int a[4][4][4][4]) {
    for (int i = 0; i < 4; ++ i )
        for (int j = 0; j < 4; ++ j )
            for (int k = 0; k < 4; ++ k )
                for (int l = 0; l < 4; ++ l )
                    a[i][j][k][l] = MIN_INF;
}

void Solve () {
    Reset(dp[0]);
    dp[0][0][0][0][0] = 0;

    for (int ind = 1; ind <= N; ++ ind ) {
        int now = ind%2;
        int old = 1 - now;
        int val = Value(ch[ind]);

        Reset(dp[now]);
        for (int i = 0; i < 4; ++ i )
            for (int j = 0; j < 4; ++ j )
                for (int k = 0; k < 4; ++ k )
                    for (int l = 0; l < 4; ++ l ) {
                        if (dp[old][i][j][k][l] == MIN_INF) continue;

                        int what = FindAdd(val, i, j);
                        dp[now][j][val][k][l] = max(dp[now][j][val][k][l], dp[old][i][j][k][l] + what);

                        what = FindAdd(val, k, l);
                        dp[now][i][j][l][val] = max(dp[now][i][j][l][val], dp[old][i][j][k][l] + what);
                    }
    }

    int ans = MIN_INF;

    for (int i = 0; i < 4; ++ i )
        for (int j = 0; j < 4; ++j )
            for (int k = 0; k < 4; ++ k )
                for (int l = 0; l < 4; ++ l )
                    ans = max(ans, dp[N%2][i][j][k][l]);

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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