제출 #351168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351168		apostoldaniel854	Miners (IOI07_miners)	C++14	68 / 100	1598 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 0;
    if (ch == 'F')
        return 1;
    return 2;
}
inline int get_dist (vector <int> &v) {
    vector <int> f (3);
    for (int x : v)
        f[x] = 1;
    return f[0] + f[1] + f[2];
}

vector <int> add (vector <int> v, int x) {
    if (v.size () < 3) {
        v.pb (x);
        return v;
    }
    else {
        return {v[1], v[2], x};
    }
}
void upd (int &a, int b) {
    if (a < b)
        a = b;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (); cout.tie (0);

    map <pair <vector <int>, vector <int>>, int> dp;
    int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    dp[{{}, {}}] = 0;
    for (char shipment : shipments_order) {
        int x = code (shipment);
        map <pair <vector <int>, vector <int>>, int> new_dp;
        for (auto prev_state : dp) {
            int value = prev_state.second;
            vector <int> first_mine = prev_state.first.first;
            vector <int> second_mine = prev_state.first.second;
            vector <int> new_first_mine = add (first_mine, x);
            vector <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));
        }
        dp = new_dp;
    }
    int ans = 0;
    for (auto state : dp)
        ans = max (ans, state.second);
    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: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8