제출 #888496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888496		Macker	Miners (IOI07_miners)	C++17	100 / 100	330 ms	286060 KiB

miners

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define mx(a, b) a = max(a, b)

int dp[100005][3][3][3][3][3][3]; //t, s1, s2, c, ss1, ss2, cc

int main()
{
    int n; cin >> n;
    string s; cin >> s;
    for (int i = 0; i < 100005; i++)
    for (int s1 = 0; s1 < 3; s1++)
    for (int s2 = 0; s2 < 3; s2++)
    for (int c = 0; c < 3; c++)
    for (int ss1 = 0; ss1 < 3; ss1++)
    for (int ss2 = 0; ss2 < 3; ss2++)
    for (int cc = 0; cc < 3; cc++){
        if(c + cc + i == 0)
            dp[i][s1][s2][c][ss1][ss2][cc] = 0;
        else
            dp[i][s1][s2][c][ss1][ss2][cc] = INT_MIN/2;
    }
    for (int i = 0; i < n; i++) {
        int a;
        if(s[i] == 'M') a = 0;
        if(s[i] == 'F') a = 1;
        if(s[i] == 'B') a = 2;

        for (int s1 = 0; s1 < 3; s1++)
        for (int s2 = 0; s2 < 3; s2++)
        for (int c = 0; c < 3; c++)
        for (int ss1 = 0; ss1 < 3; ss1++)
        for (int ss2 = 0; ss2 < 3; ss2++)
        for (int cc = 0; cc < 3; cc++){
            if(c == 0){
                mx(dp[i + 1][a][s1][1][ss1][ss2][cc], dp[i][s1][s2][0][ss1][ss2][cc] + 1);
            }
            else if(c == 1){
                int v = 1 + (a != s1);
                mx(dp[i + 1][a][s1][2][ss1][ss2][cc], dp[i][s1][s2][1][ss1][ss2][cc] + v);
            }
            else if(c == 2){
                int v = 1 + ((a != s1) && (a != s2)) + (s1 != s2);
                mx(dp[i + 1][a][s1][2][ss1][ss2][cc], dp[i][s1][s2][2][ss1][ss2][cc] + v);
            }

            if(cc == 0){
                mx(dp[i + 1][s1][s2][c][a][ss1][1], dp[i][s1][s2][c][ss1][ss2][0] + 1);
            }
            else if(cc == 1) {
                int v = 1 + (a != ss1);
                mx(dp[i + 1][s1][s2][c][a][ss1][2], dp[i][s1][s2][c][ss1][ss2][1] + v);
            }
            else if(cc == 2){
                int v = 1 + ((a != ss1) && (a != ss2)) + (ss1 != ss2);
                mx(dp[i + 1][s1][s2][c][a][ss1][2], dp[i][s1][s2][c][ss1][ss2][2] + v);
            }
        }
    }
    int res = 0;
    for (int s1 = 0; s1 < 3; s1++)
        for (int s2 = 0; s2 < 3; s2++)
        for (int c = 0; c < 3; c++)
        for (int ss1 = 0; ss1 < 3; ss1++)
        for (int ss2 = 0; ss2 < 3; ss2++)
        for (int cc = 0; cc < 3; cc++){
        mx(res, dp[n][s1][s2][c][ss1][ss2][cc]);
    }
    cout << res << endl;
}

• 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