제출 #351172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351172		apostoldaniel854	Miners (IOI07_miners)	C++14	52 / 100	1585 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, 0);
    while (mask) {
        f[mask & 3] = 1;
        mask /= 4;
    }
    return f[1] + f[2] + f[3];
}

inline int add (int mask, int x) {
    return (mask * 4 + x) & MAX_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