oj.uz

Submission #334179

# Submission time Handle Problem Language Result Execution time Memory
334179 2020-12-08T14:18:34 Z blue Miners (IOI07_miners) C++11
100 / 100
 134 ms 876 KB 
#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int a[N+1];
    char c;
    for(int i = 1; i <= N; i++)
    {
        cin >> c;
        if(c == 'M') a[i] = 1;
        else if(c == 'F') a[i] = 2;
        else if(c == 'B') a[i] = 3;
    }

    if(N == 1)
    {
        cout << "1\n";
        return 0;
    }

    if(N == 2)
    {
        cout << 2 + (a[1] != a[2]) << '\n';
        return 0;
    }

    int res = N;

    //mine 1 new, mine 1 old, mine 2 new, mine 2 old
    //0 = blank
    int dp_new[4][4][4][4], dp_old[4][4][4][4];
    for(int i = 0; i <= 3; i++) for(int j = 0; j <= 3; j++)
    for(int k = 0; k <= 3; k++) for(int l = 0; l <= 3; l++)
        dp_old[i][j][k][l] = -2000000000;

    dp_old[0][0][0][0] = 0;
    for(int n = 1; n <= N; n++)
    {
        for(int i = 0; i <= 3; i++) for(int j = 0; j <= 3; j++)
        for(int k = 0; k <= 3; k++) for(int l = 0; l <= 3; l++)
            dp_new[i][j][k][l] = -2000000000;

        for(int j = 0; j <= 3; j++)
        for(int k = 0; k <= 3; k++) for(int l = 0; l <= 3; l++)
        {
            if(j == 0) dp_new[a[n]][0][k][l] = dp_new[k][l][a[n]][0] = dp_old[0][0][k][l] + 1;
            else if(j == a[n])
            {
                for(int x = 0; x <= 3; x++)
                    dp_new[a[n]][a[n]][k][l] = dp_new[k][l][a[n]][a[n]] = max(dp_new[a[n]][a[n]][k][l], dp_old[a[n]][x][k][l] + 1 + (x != a[n] && x != 0));
            }
            else
            {
                for(int x = 0; x <= 3; x++)
                    dp_new[a[n]][j][k][l] = dp_new[k][l][a[n]][j] = max(dp_new[a[n]][j][k][l], dp_old[j][x][k][l] + 2 + (x != a[n] && x != j && x != 0));
            }

            if(n == N) res = max(res, dp_new[a[n]][j][k][l]);
        }

        swap(dp_new, dp_old);
    }

    cout << res << '\n';
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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