oj.uz

Submission #1011401

# Submission time Handle Problem Language Result Execution time Memory
1011401 2024-06-30T13:10:27 Z kaopj Miners (IOI07_miners) C++17
100 / 100
 77 ms 100900 KB 
#include <iostream>
#include <string.h>
#define lgm cin.tie(0)->sync_with_stdio(0);
using namespace std;
signed main() {
    lgm;
    int n;
    cin >> n;
    char x[n+1];
    int c[n];
    cin >> x;
    for (int i=0;i<n;i++) {
        if (x[i] == 'M') {
            c[i]=0;
        } else if (x[i] == 'B') {
            c[i]=1;
        } else {
            c[i]=2;
        }
    }
    int dp[n+1][4][4][4][4];
    memset(dp,0,sizeof dp);
    int mx=0;
    for (int i=1;i<=n;i++) {
        for (int p1=0;p1<3;p1++) {
            for (int p2=0;p2<3;p2++) {
                for (int q1=0;q1<3;q1++) {
                    for (int q2=0;q2<3;q2++) {
                        int cnt1,cnt2;
                        if (p1 == p2 && c[i-1] == p1) {
                            cnt1=1;
                        } else if (p1 ^ p2 && c[i-1] ^ p1 && c[i-1] ^ p2) {
                            cnt1=3;
                        } else {
                            cnt1=2;
                        }
                        if (q1 == q2 && c[i-1] == q1) {
                            cnt2=1;
                        } else if (q1 ^ q2 && c[i-1] ^ q1 && c[i-1] ^ q2) {
                            cnt2=3;
                        } else {
                            cnt2=2;
                        }
                        dp[i][p2][c[i-1]][q1][q2]=max(dp[i][p2][c[i-1]][q1][q2],dp[i-1][p1][p2][q1][q2]+cnt1);
                        mx=max(mx,dp[i][p2][c[i-1]][q1][q2]);
                        dp[i][p1][p2][q2][c[i-1]]=max(dp[i][p1][p2][q2][c[i-1]],dp[i-1][p1][p2][q1][q2]+cnt2);
                        mx=max(mx,dp[i][p1][p2][q2][c[i-1]]);
                    }
                }
            }
        }
    }
    cout << mx-6;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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