Submission #749230

#	Time	Username	Problem	Language	Result	Execution time	Memory
749230		Desh03	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	7 ms	704 KiB

ho_t3

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

map<int, int> mp;
set<int> x;
multiset<int> y;
int l;
vector<vector<vector<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] != -1) return dp[s][ll][rr];
    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]);
    return dp[s][ll][rr] = 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);
    }
    dp = vector<vector<vector<int>>> (2, vector<vector<int>> (n + 1, vector<int> (n + 1, -1)));
    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