Submission #536658

#	Time	Username	Problem	Language	Result	Execution time	Memory
536658		timreizin	Miners (IOI07_miners)	C++17	100 / 100	899 ms	664 KiB

miners

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <array>
#include <set>

using namespace std;

using ll = long long;

array<int, 4> itod(int j)
{
    array<int, 4> dim;
    for (int i = 0; i < 4; ++i)
    {
        dim[i] = j % 4;
        j /= 4;
    }
    return dim;;
}

int dtoi(array<int, 4> &dim)
{
    int j = 0;
    for (int i = 3; i >= 0; --i) j = j * 4 + dim[i];
    return j;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;
    array<int, 256> dp, ndp;
    for (int i = 0; i < 256; ++i) dp[i] = -1e9;
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = (s[i] == 'M' ? 1 : (s[i] == 'F' ? 2 : 3));
        for (int j = 0; j < 256; ++j) ndp[j] = -1e9;
        for (int j = 0; j < 256; ++j)
        {
            if (dp[j] == -1e9) continue;
            array<int, 4> dim = itod(j);
            if ((dim[1] == 0 && dim[0] != 0) || (dim[3] == 0 && dim[2] != 0)) continue;
            set<int> help{dim[0], dim[1], l};
            help.erase(0);
            array<int, 4> ndim = dim;
            ndim[0] = ndim[1];
            ndim[1] = l;
            int ind = dtoi(ndim);
            ndp[ind] = max(ndp[ind], dp[j] + (int)help.size());
            ndim = dim;
            help = set<int>{dim[2], dim[3], l};
            help.erase(0);
            ndim[2] = ndim[3];
            ndim[3] = l;
            ind = dtoi(ndim);
            ndp[ind] = max(ndp[ind], dp[j] + (int)help.size());
        }
        swap(dp, ndp);
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

• 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