제출 #749246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749246		Desh03	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	116 ms	1860 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long

map<int, int> mp;
set<int> x;
multiset<int> y;
int l;
vector<vector<vector<pair<int, int>>>> dp;

int recurse(int cur, int t, bool s, int ll, int rr) {
    if (x.empty() || *--y.end() < t) return 0;
    if (dp[s][ll][rr].first < t) return dp[s][ll][rr].second;
    auto it = x.upper_bound(cur);
    bool k = 0;
    if (it == x.begin()) k = 1, it = --x.end();
    else --it;
    int p = *it;
    x.erase(p);
    y.erase(y.find(mp[p]));
    int cost = (k ? cur + l - p : cur - p);
    int g = (t + cost <= mp[p]) + recurse(p, t + cost, 0, ll + 1, rr);
    x.insert(p);
    y.insert(mp[p]);
    it = x.upper_bound(cur);
    k = 0;
    if (it == x.end()) k = 1, it = x.begin();
    p = *it;
    cost = (k ? l - cur + p : p - cur);
    x.erase(p);
    y.erase(y.find(mp[p]));
    g = max(g, (t + cost <= mp[p]) + recurse(p, t + cost, 1, ll, rr + 1));
    x.insert(p);
    y.insert(mp[p]);
    if (g == dp[s][ll][rr].second) dp[s][ll][rr] = min(dp[s][ll][rr], {t, g});
    else if (g > dp[s][ll][rr].second) dp[s][ll][rr] = {t, g};
    return dp[s][ll][rr].second;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        x.insert(k);
    }
    dp = vector<vector<vector<pair<int, int>>>> (2, vector<vector<pair<int, int>>> (n, vector<pair<int, int>> (n, {1e18, 0})));
    for (auto k : x) cin >> mp[k], y.insert(mp[k]);
    cout << recurse(0, 0, 0, 0, 0) << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75