oj.uz

Submission #537364

# Submission time Handle Problem Language Result Execution time Memory
537364 2022-03-15T03:40:43 Z andecaandeci Miners (IOI07_miners) C++17
100 / 100
 1148 ms 146704 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int dp[N][4][4][4][4];
map<char, int>m;

int n;
string s;

void init(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 4; k++){
                for(int l = 0; l < 4; l++){
                    for(int m = 0; m < 4; m++)
                        dp[i][j][k][l][m] = -1;
                }
            }
        }
    }
}

int f(int idx, int la2, int la1, int lb2, int lb1){
    if(idx == n) return 0;

    int &cur = dp[idx][la2][la1][lb2][lb1];

    if(cur != -1) return cur;

    set<int>s1, s2;
    
    if(la2 > 0) s1.insert(la2);
    if(la1 > 0) s1.insert(la1);
    if(lb2 > 0) s2.insert(lb2);
    if(lb1 > 0) s2.insert(lb1);

    s1.insert(m[s[idx]]);
    s2.insert(m[s[idx]]);

    int score1, score2;
    score1 = s1.size(); score2 = s2.size();

    cur = max(
        f(idx + 1, la1, m[s[idx]], lb2, lb1) + score1,
        f(idx + 1, la2, la1, lb1, m[s[idx]]) + score2
    );

    return cur;
}

int main(){
    init();
    cin >> n;
    cin >> s;

    m['M'] = 1;
    m['B'] = 2;
    m['F'] = 3;

    cout << f(0, 0, 0, 0, 0) << endl;

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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