Submission #1275013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275013		MisterReaper	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	438 ms	444604 KiB

ho_t3

// File stamps3.cpp created on 01.10.2025 at 09:22:52
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T> 
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, L;
    std::cin >> N >> L;

    std::vector<int> X(N), T(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> T[i];
    }

    auto dist = [&](int a, int b) -> i64 {
        if (a > b) {
            std::swap(a, b);
        }
        return std::min(b - a, L - b + a);
    };

    std::vector f(N, std::vector(N, std::vector(N + 1, std::vector<i64>(2, inf))));
    for (int i = 0; i < N; ++i) {
        chmin(f[i][i][0][0], dist(0, X[i]));
        chmin(f[i][i][0][1], dist(0, X[i]));
        if (dist(0, X[i]) <= T[i]) {
            chmin(f[i][i][1][0], dist(0, X[i]));
            chmin(f[i][i][1][1], dist(0, X[i]));
        }
    }
    for (int len = 1; len <= N - 1; ++len) {
        for (int l = 0; l < N; ++l) {
            int r = (l + len - 1) % N;
            for (int t = 0; t <= N; ++t) {
                int nl = (N + l - 1) % N;
                int nr = (r + 1) % N;
                if (f[l][r][t][0] != inf) {
                    chmin(f[nl][r][t][0], f[l][r][t][0] + dist(X[l], X[nl]));
                    if (f[l][r][t][0] + dist(X[l], X[nl]) <= T[nl]) {
                        chmin(f[nl][r][t + 1][0], f[l][r][t][0] + dist(X[l], X[nl]));
                    }
                    chmin(f[l][nr][t][0], f[l][r][t][0] + dist(X[l], X[l]));
                    chmin(f[l][nr][t][1], f[l][r][t][0] + dist(X[l], X[nr]));
                    if (f[l][r][t][0] + dist(X[l], X[nr]) <= T[nr]) {
                        chmin(f[l][nr][t + 1][1], f[l][r][t][0] + dist(X[l], X[nr]));
                    }
                }
                if (f[l][r][t][1] != inf) {
                    chmin(f[nl][r][t][0], f[l][r][t][1] + dist(X[r], X[nl]));
                    if (f[l][r][t][1] + dist(X[r], X[nl]) <= T[nl]) {
                        chmin(f[nl][r][t + 1][0], f[l][r][t][1] + dist(X[r], X[nl]));
                    }
                    chmin(f[nl][r][t][1], f[l][r][t][1] + dist(X[r], X[r]));
                    chmin(f[l][nr][t][1], f[l][r][t][1] + dist(X[r], X[nr]));
                    if (f[l][r][t][1] + dist(X[r], X[nr]) <= T[nr]) {
                        chmin(f[l][nr][t + 1][1], f[l][r][t][1] + dist(X[r], X[nr]));
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int l = 0; l < N; ++l) {
        int r = (l + N - 1) % N;
        for (int t = 0; t <= N; ++t) {
            if (f[l][r][t][0] != inf) {
                ans = std::max(ans, t);
            }
            if (f[l][r][t][1] != inf) {
                ans = std::max(ans, t);
            }
        }
    }

    std::cout << ans << '\n';

    return 0;
}

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