Submission #267123

#	Time	Username	Problem	Language	Result	Execution time	Memory
267123		hhh07	Miners (IOI07_miners)	C++14	100 / 100	192 ms	201076 KiB

miners

#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 / 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