Submission #1269598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269598		rafamiune	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	0 ms	320 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 205;
const long long INF = 1e18;

int n, L;
vector<int> X(MAXN), T(MAXN);

// distância do ponto inicial (0) até um stamp i
int start_dist(int i) {
    return min(X[i], L - X[i]);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> L;
    for (int i = 1; i <= n; i++) cin >> X[i];
    for (int i = 1; i <= n; i++) cin >> T[i];

    // dp[l][r][side] = tempo mínimo para visitar [l..r]
    // side = 0 → termina em l
    // side = 1 → termina em r
    static long long dp[MAXN][MAXN][2];
    for (int l = 1; l <= n; l++)
        for (int r = 1; r <= n; r++)
            dp[l][r][0] = dp[l][r][1] = INF;

    int ans = 0;

    // casos base: intervalos unitários
    for (int i = 1; i <= n; i++) {
        // indo direto (clockwise)
        if (X[i] <= T[i]) {
            dp[i][i][0] = min(dp[i][i][0], (long long)X[i]);
            dp[i][i][1] = min(dp[i][i][1], (long long)X[i]);
            ans = max(ans, 1LL);
        }
        // indo pelo outro lado (counter-clockwise)
        if (L - X[i] <= T[i]) {
            dp[i][i][0] = min(dp[i][i][0], (long long)(L - X[i]));
            dp[i][i][1] = min(dp[i][i][1], (long long)(L - X[i]));
            ans = max(ans, 1LL);
        }
    }

    // expandindo intervalos
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            // termina em l
            // vindo de l+1 → l
            if (dp[l+1][r][0] < INF) {
                long long time = dp[l+1][r][0] + (X[l+1] - X[l]);
                if (time <= T[l]) dp[l][r][0] = min(dp[l][r][0], time);
            }
            // vindo de r → l
            if (dp[l+1][r][1] < INF) {
                long long time = dp[l+1][r][1] + (X[r] - X[l]);
                if (time <= T[l]) dp[l][r][0] = min(dp[l][r][0], time);
            }

            // termina em r
            // vindo de r-1 → r
            if (dp[l][r-1][1] < INF) {
                long long time = dp[l][r-1][1] + (X[r] - X[r-1]);
                if (time <= T[r]) dp[l][r][1] = min(dp[l][r][1], time);
            }
            // vindo de l → r
            if (dp[l][r-1][0] < INF) {
                long long time = dp[l][r-1][0] + (X[r] - X[l]);
                if (time <= T[r]) dp[l][r][1] = min(dp[l][r][1], time);
            }

            if (dp[l][r][0] < INF || dp[l][r][1] < INF)
                ans = max(ans, (int)(r - l + 1));
        }
    }

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

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