제출 #484733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484733		Alexandruabcde	Miners (IOI07_miners)	C++14	100 / 100	119 ms	496 KiB

miners

#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 / 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