Submission #157747

#	Time	Username	Problem	Language	Result	Execution time	Memory
157747		stefdasca	Miners (IOI07_miners)	C++14	100 / 100	238 ms	576 KiB

miners

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int dp[2][4][4][9][9];
bool viz[2][4][4][9][9];
int can[4][27], md[27];
int p3[] = {1, 3, 9};
int counter[4][27];
int nr(char c)
{
    if(c == 'B')
        return 0;
    if(c == 'M')
        return 1;
    return 2;
}
int proc(int hm, int nr)
{
    vector<int>c;
    for(int i = hm-1; i >= 0; --i)
    {
        c.push_back(nr / p3[i]);
        nr %= p3[i];
    }
    int ans = 1;
    sort(c.begin(), c.end());
    for(int i = 1; i < c.size(); ++i)
        ans = ans + (c[i] > c[i-1]);
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> s;
    s = ' ' + s;

    for(int i = 0; i <= 26; ++i)
        md[i] = i%9;
    can[0][0] = can[1][0] = can[2][0] = can[3][0] = 1;
    for(int i = 1; i <= 2; ++i)
        can[1][i] = can[2][i] = can[3][i] = 1;
    for(int i = 3; i <= 8; ++i)
        can[2][i] = can[3][i] = 1;
    for(int i = 9; i <= 26; ++i)
        can[3][i] = 1;

    for(int i = 0; i <= 26; ++i)
        for(int j = 1; j <= 3; ++j)
            if(can[j][i])
                counter[j][i] = proc(j, i);

    viz[0][0][0][0][0] = 1;

    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        s[i] = nr(s[i]);
        int prv = (i-1) % 2;
        int cur = i % 2;
        for(int cf = 0; cf <= 3; ++cf)
            for(int prev = 0; prev <= 8; ++prev)
            {
                if(!can[cf][prev])
                    continue;
                for(int cf2 = 0; cf2 <= 3; ++cf2)
                    for(int prev2 = 0; prev2 <= 8; ++prev2)
                    {
                        if(!can[cf2][prev])
                            continue;
                        if(!viz[prv][cf][cf2][prev][prev2])
                            continue;
                        if(dp[prv][cf][cf2][prev][prev2] + 10 <= ans)
                            continue;

                        int new_state = md[prev] * 3 + s[i];
                        int new_cf = cf+1;
                        if(new_cf == 4)
                            new_cf = 3;
                        viz[cur][new_cf][cf2][md[new_state]][prev2] = 1;
                        dp[cur][new_cf][cf2][md[new_state]][prev2] = max(dp[cur][new_cf][cf2][md[new_state]][prev2], dp[prv][cf][cf2][prev][prev2] + counter[new_cf][new_state]);
                        ans = max(ans, dp[cur][new_cf][cf2][md[new_state]][prev2]);


                        new_state = md[prev2] * 3 + s[i];
                        new_cf = cf2 + 1;
                        if(new_cf == 4)
                            new_cf = 3;
                        viz[cur][cf][new_cf][prev][md[new_state]] = 1;
                        dp[cur][cf][new_cf][prev][md[new_state]] = max(dp[cur][cf][new_cf][prev][md[new_state]], dp[prv][cf][cf2][prev][prev2] + counter[new_cf][new_state]);

                        ans = max(ans, dp[cur][cf][new_cf][prev][md[new_state]]);
                    }
            }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int proc(int, int)':
miners.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < c.size(); ++i)
                    ~~^~~~~~~~~~

• 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