oj.uz

Submission #411285

# Submission time Handle Problem Language Result Execution time Memory
411285 2021-05-24T23:06:15 Z couplefire Miners (IOI07_miners) C++17
100 / 100
 137 ms 640 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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