oj.uz

Submission #685371

# Submission time Handle Problem Language Result Execution time Memory
685371 2023-01-24T08:00:33 Z finn__ Miners (IOI07_miners) C++17
100 / 100
 1090 ms 448 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 280 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 212 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 284 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 312 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 448 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1090 ms 320 KB Output is correct