Submission #351171

#	Time	Username	Problem	Language	Result	Execution time	Memory
351171		apostoldaniel854	Miners (IOI07_miners)	C++14	52 / 100	1591 ms	620 KiB

miners

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

int code (char ch) {
    if (ch == 'M')
        return 1;
    if (ch == 'F')
        return 2;
    return 3;
}
const int MAX_MASK = (1 << 6) - 1;
inline int get_dist (int mask) {
    vector <int> f (4);
    while (mask) {
        f[mask % 4] = 1;
        mask /= 4;
    }
    return f[1] + f[2] + f[3];
}

inline int add (int mask, int x) {
    mask *= 4;
    mask += x;
    mask &= MAX_MASK;
    return mask;
}
inline void upd (int &a, int b) {
    if (a < b)
        a = b;
}

int dp[MAX_MASK][MAX_MASK];
int new_dp[MAX_MASK][MAX_MASK];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (); cout.tie (0);

    int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
            dp[first_mine][second_mine] = -1;
    dp[0][0] = 0;
    for (char shipment : shipments_order) {
        int x = code (shipment);
        for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                new_dp[first_mine][second_mine] = -1;
        for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++) {
                int value = dp[first_mine][second_mine];
                if (value >= 0) {
                    int new_first_mine = add (first_mine, x);
                    int new_second_mine = add (second_mine, x);
                    upd (new_dp[new_first_mine][second_mine], value + get_dist (new_first_mine));
                    upd (new_dp[first_mine][new_second_mine], value + get_dist (new_second_mine));
                }
            }
        for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                dp[first_mine][second_mine] = new_dp[first_mine][second_mine];
    }
    int ans = 0;
    for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
            upd (ans, dp[first_mine][second_mine]);
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 8 / 8
• Subtask 8: 0 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8