Submission #411285

#	Time	Username	Problem	Language	Result	Execution time	Memory
411285		couplefire	Miners (IOI07_miners)	C++17	100 / 100	137 ms	640 KiB

miners

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
const int INF = 1e9;

int ckmax(int &a, int b){return (b>a)?a=b:b;}

int n;
string s;
int dp[2][4][4][4][4];

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s; s = "$"+s;
    for(int i = 1; i<=n; i++)
        if(s[i] == 'M') s[i] = '1';
        else if(s[i] == 'F') s[i] = '2';
        else s[i] = '3';
    memset(dp, -1, sizeof dp);
    dp[0][0][0][0][0] = 0;
    for(int i = 1; i<=n; i++){
        memset(dp[1], -1, sizeof dp[1]);
        int x = s[i]-'0';
        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(dp[0][a][b][c][d] == -1) continue;
                        if(a!=b && a!= x && b != x && a != 0 && b != 0)
                            ckmax(dp[1][b][x][c][d], dp[0][a][b][c][d]+3);
                        else if((a == b && b == x)||(a == 0 && b == x)||(b == 0 && a == x)||(a == 0 && b == 0))
                            ckmax(dp[1][b][x][c][d], dp[0][a][b][c][d]+1);
                        else
                            ckmax(dp[1][b][x][c][d], dp[0][a][b][c][d]+2);
                        if(c!=d && c!= x && d != x && c != 0 && d != 0)
                            ckmax(dp[1][a][b][d][x], dp[0][a][b][c][d]+3);
                        else if((c == d && d == x)||(c == 0 && d == x)||(d == 0 && c == x)||(c == 0 && d == 0))
                            ckmax(dp[1][a][b][d][x], dp[0][a][b][c][d]+1);
                        else
                            ckmax(dp[1][a][b][d][x], dp[0][a][b][c][d]+2);
                    }
        swap(dp[0], dp[1]);
    }
    int ans = 0;
    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++)
                    ckmax(ans, dp[0][a][b][c][d]);
    cout << ans << endl;
}

• 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