제출 #1269597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269597		rafamiune	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	320 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
const int MAXN = 205;
const long long INF = 1e18;

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

// distância mínima circular entre dois stamps
int dist(int i, int j) {
    int d = abs(X[i] - X[j]);
    return min(d, L - d);
}

// 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 todos [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;

    // base: intervalos unitários
    for (int i = 1; i <= n; i++) {
        int d = start_dist(i);
        if (d <= T[i]) {
            dp[i][i][0] = dp[i][i][1] = d;
            ans = 1;
        }
    }

    // transições
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            // termina em l
            // caso venha de l+1
            if (dp[l+1][r][0] < INF) {
                long long time = dp[l+1][r][0] + dist(l, l+1);
                if (time <= T[l]) dp[l][r][0] = min(dp[l][r][0], time);
            }
            // caso venha de r
            if (dp[l+1][r][1] < INF) {
                long long time = dp[l+1][r][1] + dist(l, r);
                if (time <= T[l]) dp[l][r][0] = min(dp[l][r][0], time);
            }

            // termina em r
            // caso venha de r-1
            if (dp[l][r-1][1] < INF) {
                long long time = dp[l][r-1][1] + dist(r-1, r);
                if (time <= T[r]) dp[l][r][1] = min(dp[l][r][1], time);
            }
            // caso venha de l
            if (dp[l][r-1][0] < INF) {
                long long time = dp[l][r-1][0] + dist(l, r);
                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, r - l + 1);
        }
    }

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

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