Submission #254900

#	Time	Username	Problem	Language	Result	Execution time	Memory
254900		imeimi2000	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	443 ms	65024 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
typedef long long llong;

const llong inf = 1e18;
int n, L;
int X[202], T[202];
llong dp[202][202][202];

int dist(int x, int y) {
    int ret = abs(X[x] - X[y]);
    return min(ret, L - ret);
}

llong get(int x, int y, int c) {
    if (c < 0) return inf;
    if (x < 0 || x > n + 1) return inf;
    if (y < 0 || y > n + 1) return inf;
    if (dp[c][x][y] != -1) return dp[c][x][y];
    llong ret = inf;
    int px = x;
    if (x < y) --px; else ++px;
    ret = min(ret, get(px, y, c) + dist(px, x));
    ret = min(ret, get(y, px, c) + dist(y, x));
    if (get(px, y, c - 1) + dist(px, x) <= T[x]) ret = min(ret, get(px, y, c - 1) + dist(px, x));
    if (get(y, px, c - 1) + dist(y, x) <= T[x]) ret = min(ret, get(y, px, c - 1) + dist(y, x));
    return dp[c][x][y] = ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> L;
    for (int i = 1; i <= n; ++i) cin >> X[i]; X[n + 1] = L;
    for (int i = 1; i <= n; ++i) cin >> T[i]; T[0] = T[n + 1] = -1;
    memset(dp, -1, sizeof(dp));
    dp[0][0][n + 1] = 0;
    dp[0][n + 1][0] = 0;
    for (int i = 1; i <= n; ++i) dp[i][0][n + 1] = dp[i][n + 1][0] = inf;
    for (int ans = n; ans > 0; --ans) {
        for (int i = 1; i <= n; ++i) {
            if (get(i - 1, i, ans) < inf || get(i, i - 1, ans) < inf) {
                printf("%d\n", ans);
                return 0;
            }
        }
    }
    printf("0\n");
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 1; i <= n; ++i) cin >> X[i]; X[n + 1] = L;
     ^~~
ho_t3.cpp:34:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (int i = 1; i <= n; ++i) cin >> X[i]; X[n + 1] = L;
                                               ^
ho_t3.cpp:35:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 1; i <= n; ++i) cin >> T[i]; T[0] = T[n + 1] = -1;
     ^~~
ho_t3.cpp:35:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (int i = 1; i <= n; ++i) cin >> T[i]; T[0] = T[n + 1] = -1;
                                               ^

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