oj.uz

Submission #888496

# Submission time Handle Problem Language Result Execution time Memory
888496 2023-12-17T14:51:57 Z Macker Miners (IOI07_miners) C++17
100 / 100
 330 ms 286060 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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