제출 #351176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351176		apostoldaniel854	Miners (IOI07_miners)	C++14	100 / 100	1217 ms	748 KiB

miners

#include <bits/stdc++.h>

using namespace std;

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

inline int code (char ch) {
    if (ch == 'M')
        return 1;
    if (ch == 'F')
        return 2;
    return 3;
}
const int MAX_MASK = (1 << 6);
int f[4];
inline int get_dist (int mask) {
    f[1] = f[2] = f[3] = 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 << 2) + x) & (MAX_MASK - 1);
}
inline void upd (int &a, int b) {
    if (a < b)
        a = b;
}

int dp[1 + MAX_MASK][1 + MAX_MASK];
int new_dp[1 + MAX_MASK][1 + MAX_MASK];

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

    register int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (register 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) {
        register int x = code (shipment);

        for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                new_dp[first_mine][second_mine] = -1;

        for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) {
                register int value = dp[first_mine][second_mine];
                if (value >= 0) {
                    register int new_first_mine = add (first_mine, x);
                    register 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 (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register  int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                dp[first_mine][second_mine] = new_dp[first_mine][second_mine];
    }

    register int ans = 0;
    for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (register 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: 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