Submission #162028

#	Time	Username	Problem	Language	Result	Execution time	Memory
162028		sans	Miners (IOI07_miners)	C++14	92 / 100	1575 ms	187652 KiB

miners

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

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(int yy = 0; yy < YY; ++yy)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;

int N;
string S;

map<string, int> conv;

vector<vector<vector<int>>> DN;

int M(int n, string state1, string state2)
{
    if(n == N) return 0;
    if(DN[n][conv[state1]][conv[state2]] != -1) return DN[n][conv[state1]][conv[state2]];

    string newstate1 = state1, newstate2 = state2;

    if(newstate1.length() == 2){ newstate1[0] = newstate1[1]; newstate1[1] = S[n]; }
    if(newstate1.empty() or newstate1.length() == 1) newstate1 += S[n];

    if(newstate2.length() == 2){ newstate2[0] = newstate2[1]; newstate2[1] = S[n]; }
    if(newstate2.empty() or newstate2.length() == 1) newstate2 += S[n];

    int value1, value2;

    if(state1.size() == 2)
    {
        if(S[n] != state1[0] and S[n] != state1[1] and state1[0] != state1[1]) value1 = 3;
        if(S[n] != state1[0] and S[n] != state1[1] and state1[0] == state1[1]) value1 = 2;
        if(S[n] == state1[0] and S[n] != state1[1]) value1 = 2;
        if(S[n] == state1[1] and S[n] != state1[0]) value1 = 2;
        if(S[n] == state1[1] and S[n] == state1[0]) value1 = 1;
    }
    if(state1.size() == 1)
    {
        if(S[n] == state1[0]) value1 = 1;
        else value1 = 2;
    }
    if(state1.empty())
    {
        value1 = 1;
    }

    if(state2.size() == 2)
    {
        if(S[n] != state2[0] and S[n] != state2[1] and state2[0] != state2[1]) value2 = 3;
        if(S[n] != state2[0] and S[n] != state2[1] and state2[0] == state2[1]) value2 = 2;
        if(S[n] == state2[0] and S[n] != state2[1]) value2 = 2;
        if(S[n] == state2[1] and S[n] != state2[0]) value2 = 2;
        if(S[n] == state2[1] and S[n] == state2[0]) value2 = 1;
    }
    if(state2.size() == 1)
    {
        if(S[n] == state2[0]) value2 = 1;
        else value2 = 2;
    }
    if(state2.empty())
    {
        value2 = 1;
    }
    
    //cout << n << sp << state1 << sp << state2 << endl;
    //cout << value1 << sp << value2 << endl << endl;
    return DN[n][conv[state1]][conv[state2]] = max( M(n+1, newstate1, state2) + value1, M(n+1, state1, newstate2) + value2 );
}

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> S;

    conv["MM"] = 1;
    conv["MB"] = 2;
    conv["MF"] = 3;
    conv["BM"] = 4;
    conv["BB"] = 5;
    conv["BF"] = 6;
    conv["FM"] = 7;
    conv["FB"] = 8;
    conv["FF"] = 9;
    conv["M"] = 11;
    conv["F"] = 12;
    conv["B"] = 13;
    conv[""]  = 14;

    DN.assign(N+1, vvi(15, vi(15, -1)));

    cout << M(0, "", "") << endl;

    return 0;
}

//cikisir

• 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: 0 / 8