Submission #685371

#	Time	Username	Problem	Language	Result	Execution time	Memory
685371		finn__	Miners (IOI07_miners)	C++17	100 / 100	1090 ms	448 KiB

miners

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

/*
Once the last two shipments of each  mine are fixed, earlier ones do no matter.
Thus, the problem has optimal substructure with 3^4 states (for each mine 9).
For each of the states, either send the current food to the first or second
mine. At the end, take the maximum of all 81 states. => O(n) * bad constant
*/

int produced_coal(array<unsigned, 3> food)
{
    sort(food.begin(), food.end());
    if (food[0] == 3)
        return 0;
    if (food[1] == 3)
        return 1;
    if (food[2] == 3)
        return food[0] == food[1] ? 1 : 2;
    return (food[0] == food[1] && food[1] == food[2])
               ? 1
               : (food[0] == food[1] || food[1] == food[2] ? 2 : 3);
}

int main()
{
    size_t n;
    cin >> n;

    int dp1[4][4][4][4], dp2[4][4][4][4];
    for (unsigned j1 = 0; j1 < 4; j1++)
        for (unsigned j2 = 0; j2 < 4; j2++)
            for (unsigned j3 = 0; j3 < 4; j3++)
                for (unsigned j4 = 0; j4 < 4; j4++)
                    dp1[j1][j2][j3][j4] = dp2[j1][j2][j3][j4] = INT_MIN;
    dp1[3][3][3][3] = 0, dp2[3][3][3][3] = 0;
    int max_coal = 0;

    for (size_t i = 0; i < n; i++)
    {
        char c;
        cin >> c;
        unsigned k = c == 'M' ? 0 : (c == 'F' ? 1 : 2);

        for (unsigned j1 = 0; j1 < 4; j1++)
            for (unsigned j2 = 0; j2 < 4; j2++)
                for (unsigned j3 = 0; j3 < 4; j3++)
                    for (unsigned j4 = 0; j4 < 4; j4++)
                    {
                        dp2[j1][j2][j4][k] = max(
                            dp2[j1][j2][j4][k],
                            dp1[j1][j2][j3][j4] + produced_coal({j3, j4, k}));
                        dp2[j2][k][j3][j4] = max(
                            dp2[j2][k][j3][j4],
                            dp1[j1][j2][j3][j4] + produced_coal({j1, j2, k}));

                        max_coal = max(max_coal, dp2[j1][j2][j4][k]);
                        max_coal = max(max_coal, dp2[j2][k][j3][j4]);
                    }

        swap(dp1, dp2);
    }

    cout << max_coal << '\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