Submission #334179

#	Time	Username	Problem	Language	Result	Execution time	Memory
334179		blue	Miners (IOI07_miners)	C++11	100 / 100	134 ms	876 KiB

miners

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