oj.uz

Submission #267123

# Submission time Handle Problem Language Result Execution time Memory
267123 2020-08-15T21:06:03 Z hhh07 Miners (IOI07_miners) C++14
100 / 100
 192 ms 201076 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>

using namespace std;

int dp[100010][4][4][4][4], moze[100010][4][4][4][4];

int cal(int a, int b, int c){
    int val[4] = {0, 0, 0};
    val[a] = 1; val[b] = 1; val[c] = 1;
    return val[1] + val[2] + val[3];
}

int main(){
    int n; string s;
    cin >> n >> s;
    
    s = '.' + s;
    
    
    
    memset(dp, 0, sizeof dp); memset(moze, false, sizeof moze);
    moze[0][0][0][0][0] = true;
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int x = 1;
        if (s[i] == 'B')
            x = 2;
        else if (s[i] == 'F')
            x = 3;
        
        for (int a = 0; a < 4; a++){
            for (int b = 0; b < 4; b++){
                for (int c = 0; c < 4; c++){
                    for (int d = 0; d < 4; d++){
                        if (!moze[i - 1][a][b][c][d])
                            continue;
                        moze[i][x][a][c][d] = true;
                        moze[i][a][b][x][c] = true;
                        dp[i][x][a][c][d] = max(dp[i][x][a][c][d], dp[i - 1][a][b][c][d] + cal(x, a, b));
                        dp[i][a][b][x][c] = max(dp[i][a][b][x][c], dp[i - 1][a][b][c][d] + cal(x, c, d));
                        ans = max(ans, max(dp[i][x][a][c][d] , dp[i][a][b][x][c]));

                    }
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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