Submission #939600

#	Time	Username	Problem	Language	Result	Execution time	Memory
939600		kitlix	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	147 ms	130440 KiB

ho_t3

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e18;

vector<vector<vector<int>>> dp[2];

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, l;
    cin >> n >> l;
    vector<int> x(n), t(n);
    for (auto& el : x)
        cin >> el;
    for (auto& el : t)
        cin >> el;
    auto dist = [&](int x1, int x2) {
        int res = (x1 - x2 + l) % l;
        res = min(res, (x2 - x1 + l) % l);
        return res;
        };
    dp[0].resize(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INF)));
    dp[1].resize(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INF)));
    dp[0][0][0][0] = 0;
    dp[1][0][0][0] = 0;
    dp[0][1][0][0] = dist(0, x[0]);
    if (dp[0][1][0][0] <= t[0])
        dp[0][1][0][1] = dp[0][1][0][0];
    dp[1][0][1][0] = dist(0, x[n - 1]);
    if (dp[1][0][1][0] <= t[n - 1])
        dp[1][0][1][1] = dp[1][0][1][0];
    for (int ln = 2; ln <= n; ++ln) {
        for (int l = 0; l <= ln; ++l) {
            int r = ln - l;
            if (l != 0) {
                for (int prevcnt = 0; prevcnt < ln; ++prevcnt) {
                    if (l - 1 != 0)
                        dp[0][l][r][prevcnt] = min(dp[0][l][r][prevcnt], dp[0][l - 1][r][prevcnt] + dist(x[l - 1], x[l - 2]));
                    if (r != 0)
                        dp[0][l][r][prevcnt] = min(dp[0][l][r][prevcnt], dp[1][l - 1][r][prevcnt] + dist(x[l - 1], x[n - r]));
                }
                for (int curcnt = ln ; curcnt > 0; --curcnt)
                    if (dp[0][l][r][curcnt - 1] <= t[l - 1])
                        dp[0][l][r][curcnt] = min(dp[0][l][r][curcnt], dp[0][l][r][curcnt - 1]);
            }
            if (r != 0) {
                for (int prevcnt = 0; prevcnt < ln; ++prevcnt) {
                    if (r - 1 != 0)
                        dp[1][l][r][prevcnt] = min(dp[1][l][r][prevcnt], dp[1][l][r - 1][prevcnt] + dist(x[n - r], x[n - r + 1]));
                    if (l != 0)
                        dp[1][l][r][prevcnt] = min(dp[1][l][r][prevcnt], dp[0][l][r - 1][prevcnt] + dist(x[n - r], x[l - 1]));
                }
                for (int curcnt = ln ; curcnt > 0; --curcnt)
                    if (dp[1][l][r][curcnt - 1] <= t[n - r])
                        dp[1][l][r][curcnt] = min(dp[1][l][r][curcnt], dp[1][l][r][curcnt - 1]);
            }
        }
    }
    for (int curcnt = n; curcnt > 0; --curcnt) {
        for (int l = 0; l <= n; ++l) {
            int r = n - l;
            if (dp[0][l][r][curcnt] != INF) {
                cout << curcnt;
                return 0;
            }
            if (dp[1][l][r][curcnt] != INF) {
                cout << curcnt;
                return 0;
            }
        }
    }
    cout << 0;
    return 0;
}

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