Submission #254896

#	Time	Username	Problem	Language	Result	Execution time	Memory
254896		imeimi2000	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	33 ms	64248 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[201][202][201];

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[x][y][c] != -1) return dp[x][y][c];
    llong ret = inf;
    int px = x, py = y;
    if (x < y) --px, ++py;
    else ++px, --py;
    ret = min(ret, get(px, y, c) + abs(X[px] - X[x]));
    ret = min(ret, get(py, x, c) + abs(X[py] - X[x]));
    if (get(px, y, c - 1) + abs(X[px] - X[x]) <= T[x]) ret = min(ret, get(px, y, c - 1) + abs(X[px] - X[x]));
    if (get(py, x, c - 1) + abs(X[py] - X[x]) <= T[x]) ret = min(ret, get(py, x, c - 1) + abs(X[py] - X[x]));
    return dp[x][y][c] = 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][n + 1][0] = 0;
    dp[n + 1][0][0] = 0;
    for (int i = 1; i <= n; ++i) dp[0][n + 1][i] = dp[n + 1][0][i] = 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:30: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:30: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:31: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:31: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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75