Submission #749201

#TimeUsernameProblemLanguageResultExecution timeMemory
749201Desh03Collecting Stamps 3 (JOI20_ho_t3)C++17
15 / 100
2061 ms404 KiB
#include <bits/stdc++.h>
using namespace std;

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

int recurse(int cur, int t) {
    if (x.empty() || *--y.end() < t) return 0;
    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);
    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));
    x.insert(p);
    y.insert(mp[p]);
    return g;
}

int 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);
    }
    for (auto k : x) cin >> mp[k], y.insert(mp[k]);
    cout << recurse(0, 0) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...