제출 #749266

#제출 시각아이디문제언어결과실행 시간메모리
749266Desh03Collecting Stamps 3 (JOI20_ho_t3)C++17
15 / 100
14 ms1236 KiB
#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;
set<int> x;
multiset<int> y;
int l;
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][s][ll][rr] != -1) return dp[w][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[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[1][s][ll][rr] = g;
    return max(dp[0][s][ll][rr], dp[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 (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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...