Submission #1265052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265052		baotoan655	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	76 ms	128840 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    long long L;
    if (!(cin >> N >> L)) return 0;
    vector<long long> X(N), T(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    for (int i = 0; i < N; ++i) cin >> T[i];

    // right[j] = đi theo chiều kim từ 0 đến tem j (1..N)
    // left[i]  = đi ngược kim từ 0 đến tem phía trái i (1..N), gần 0 dần khi i tăng
    vector<long long> right(N+1, 0), left(N+1, 0);
    for (int j = 1; j <= N; ++j) right[j] = X[j-1];
    for (int i = 1; i <= N; ++i) left[i] = L - X[N - i];

    // ánh xạ sang chỉ số tem gốc để lấy deadline
    vector<int> idxR(N+1), idxL(N+1);
    idxR[0] = -1; // không dùng
    idxL[0] = -1;
    for (int j = 1; j <= N; ++j) idxR[j] = j - 1;          // tem X[j-1]
    for (int i = 1; i <= N; ++i) idxL[i] = N - i;          // tem X[N-i]

    const long long INF = (long long)4e18;

    // dpL[i][j][k], dpR[i][j][k]
    static long long dpL[202][202][202];
    static long long dpR[202][202][202];
    for (int i = 0; i <= N; ++i)
        for (int j = 0; j <= N; ++j)
            for (int k = 0; k <= N; ++k)
                dpL[i][j][k] = dpR[i][j][k] = INF;

    dpL[0][0][0] = dpR[0][0][0] = 0;  // xuất phát ở 0, chưa ghé tem nào

    auto distLR = [&](long long aL, long long bR)->long long {
        // khoảng cách giữa điểm ở trái cách 0 là aL và điểm ở phải cách 0 là bR
        long long s = aL + bR;
        return min(s, L - s);
    };

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j + i <= N; ++j) {
            int visited = i + j; // số tem đã GHÉ (có thể có cái trễ hạn)
            for (int k = 0; k <= visited; ++k) {
                long long cur;

                // Đang ở TRÁI
                cur = dpL[i][j][k];
                if (cur < INF && visited < N) {
                    // đi tiếp 1 tem ở TRÁI: left[i] -> left[i+1]
                    long long arrive = cur + (left[i+1] - left[i]);
                    int id = idxL[i+1];
                    int nk = k + (arrive <= T[id] ? 1 : 0);
                    dpL[i+1][j][nk] = min(dpL[i+1][j][nk], arrive);

                    // nhảy sang tem tiếp theo ở PHẢI
                    arrive = cur + distLR(left[i], right[j+1]);
                    id = idxR[j+1];
                    nk = k + (arrive <= T[id] ? 1 : 0);
                    dpR[i][j+1][nk] = min(dpR[i][j+1][nk], arrive);
                }

                // Đang ở PHẢI
                cur = dpR[i][j][k];
                if (cur < INF && visited < N) {
                    // đi tiếp 1 tem ở PHẢI: right[j] -> right[j+1]
                    long long arrive = cur + (right[j+1] - right[j]);
                    int id = idxR[j+1];
                    int nk = k + (arrive <= T[id] ? 1 : 0);
                    dpR[i][j+1][nk] = min(dpR[i][j+1][nk], arrive);

                    // nhảy sang tem tiếp theo ở TRÁI
                    arrive = cur + distLR(left[i+1], right[j]);
                    id = idxL[i+1];
                    nk = k + (arrive <= T[id] ? 1 : 0);
                    dpL[i+1][j][nk] = min(dpL[i+1][j][nk], arrive);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= N; ++i)
        for (int j = 0; j + i <= N; ++j)
            for (int k = 0; k <= N; ++k)
                if (dpL[i][j][k] < INF || dpR[i][j][k] < INF)
                    ans = max(ans, k);

    cout << ans << '\n';
    return 0;
}

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