Submission #749269

#	Time	Username	Problem	Language	Result	Execution time	Memory
749269		Desh03	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	28 ms	2260 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<vector<vector<int>>>>> dp;

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

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 (2, vector (2, vector(2, vector (n, vector<int> (n, -1)))));
    for (auto k : x) cin >> mp[k], y.insert(mp[k]);
    cout << recurse(0, 0, 0, 0, 0, 0) << '\n';
}

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