Submission #796940

#	Time	Username	Problem	Language	Result	Execution time	Memory
796940		cfhater	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	308 ms	65128 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
// #define int ll

const ll INF = 1e18;
const int MAXN = 201, MOD = 1e9 + 7;

int n, l;
ll dp[MAXN][MAXN][MAXN][2];

inline ll dist(int a, int b) {
    return min(((a - b) % l + l) % l, ((b - a) % l + l) % l);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> l;
    vector<pair<int, int>> left(n);
    for (auto& i : left)
        cin >> i.first;
    for (auto& i : left)
        cin >> i.second;
    auto right = left;
    left.push_back({0, 0});
    right.push_back({l, 0});
    sort(all(left));
    sort(rall(right));

    int res = 0;
    for (int lb = 0; lb <= n; lb++)
        for (int rb = 0; lb + rb <= n; rb++)
            for (int cnt = 0; cnt <= n; cnt++)
                dp[lb][rb][cnt][0] = dp[lb][rb][cnt][1] = INF;
    for (int lb = 1; lb <= n; lb++) {
        if (dist(0, left[lb].first) <= left[lb].second) {
            dp[lb][0][1][0] = dist(0, left[lb].first);
            dp[lb][0][1][1] = dp[lb][0][1][0] * 2;
            res = 1;
        }
    }
    for (int rb = 1; rb <= n; rb++) {
        if (dist(0, right[rb].first) <= right[rb].second) {
            dp[0][rb][1][1] = dist(0, right[rb].first);
            dp[0][rb][1][0] = dp[0][rb][1][1] * 2;
            res = 1;
        }
    }

    for (int cnt = 1; cnt <= n; cnt++) {
        for (int lb = 0; lb <= n; lb++) {
            for (int rb = 0; lb + rb <= n; rb++) {
                if (lb > 0)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt][1] + dist(right[rb].first, left[lb].first));
                if (lb > 0)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt][0] + dist(left[lb - 1].first, left[lb].first));
                if (lb > 0 and dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first) <= left[lb].second)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first));
                if (lb > 0 and dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first) <= left[lb].second)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first));

                if (rb > 0)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt][0] + dist(left[lb].first, right[rb].first));
                if (rb > 0)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt][1] + dist(right[rb - 1].first, right[rb].first));
                if (rb > 0 and dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first) <= right[rb].second)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first));
                if (rb > 0 and dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first) <= right[rb].second)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first));

                if (dp[lb][rb][cnt][0] != INF or dp[lb][rb][cnt][1] != INF)
                    res = max(res, cnt);
            }
        }
    }

    cout << res;
}

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