Submission #334178

#TimeUsernameProblemLanguageResultExecution timeMemory
334178blueMiners (IOI07_miners)C++11
100 / 100
137 ms748 KiB
#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++)
    {
        //cout << "\n\n\n 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++)
        {

            //i, j, k, l belong to three options, {0, a[n] and !a[n]}

            //Insert code below

            //i is assumed to be a[n], and can be swapped with k
            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]);
            //cout << j << ' ' << k << ' ' << l << " -> " << dp_new[a[n]][j][k][l] << '\n';
        }

        swap(dp_new, dp_old);
    }

    cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...