제출 #1288019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288019		BlockOG	Miners (IOI07_miners)	C++20	100 / 100	166 ms	648 KiB

miners

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return 0;
}();

int calc_add(int i) {
    int r[3] = {0, 0, 0};
    r[i / 1 % 3] = 1;
    r[i / 3 % 3] = 1;
    r[i / 9 % 3] = 1;

    return r[0] + r[1] + r[2];
}

int full(int a) {
    return a + a * 3 + a * 9;
}

int change(int i, int a) {
    return i % 27 / 3 + a * 9;
}

int main() {
    string s; cin >> s >> s;

    array<int, 27> lo, ln;
    array<int, 27> ro, rn;
    array<int, 729> o, n;
    lo.fill(INT_MIN), ro.fill(INT_MIN), o.fill(INT_MIN);

    lo[full(s[0] == 'M' ? 0 : s[0] == 'F' ? 1 : 2)] = 1;
    ro[full(s[0] == 'M' ? 0 : s[0] == 'F' ? 1 : 2)] = 1;

    fo(i, 1, s.size()) {
        int a = s[i] == 'M' ? 0 : s[i] == 'F' ? 1 : 2;

        ln.fill(INT_MIN), rn.fill(INT_MIN), n.fill(INT_MIN);
        fo(j, 0, 27) {
            ln[change(j, a)] = max(ln[change(j, a)], lo[j] + calc_add(change(j, a)));
            n[j + full(a) * 27] = max(n[j + full(a) * 27], lo[j] + 1);

            rn[change(j, a)] = max(rn[change(j, a)], ro[j] + calc_add(change(j, a)));
            n[full(a) + j * 27] = max(n[full(a) + j * 27], ro[j] + 1);

            fo(k, 0, 27) {
                n[change(j, a) + k * 27] = max(n[change(j, a) + k * 27], o[j + k * 27] + calc_add(change(j, a)));
                n[k + change(j, a) * 27] = max(n[k + change(j, a) * 27], o[k + j * 27] + calc_add(change(j, a)));
            }
        }

        swap(lo, ln), swap(ro, rn), swap(o, n);
    }

    int res = 0;
    for (int i : lo) res = max(res, i);
    for (int i : ro) res = max(res, i);
    for (int i : o) res = max(res, i);
    cout << res;
}

• 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