Submission #563663

#	Time	Username	Problem	Language	Result	Execution time	Memory
563663		4fecta	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	678 ms	135260 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 205;

int n, L, x[MN], t[MN], dp[MN][MN][MN][2], ans; //left, right, how many, left/right = min time

int d(int i, int j) {
    i %= (n + 1), j %= (n + 1);
    if (i < j) swap(i, j);
    int p1 = L - x[i] + x[j], p2 = L - p1;
    return min(p1, p2);
}

int rec(int l, int r, int k, int s) {
    l %= (n + 1), r %= (n + 1);
    //printf("%d %d %d %d\n", l, r, k, s);
    if (dp[l][r][k][s] != -1) return dp[l][r][k][s];
    int bst = 1e12;
    if (!s && l > 0) {
        bst = min(bst, rec(l + 1, r, k, 1) + d(l, r));
        bst = min(bst, rec(l + 1, r, k, 0) + d(l, l + 1));
        if (k) {
            int v1 = rec(l + 1, r, k - 1, 1) + d(l, r);
            if (v1 <= t[l]) bst = min(bst, v1);
            int v2 = rec(l + 1, r, k - 1, 0) + d(l, l + 1);
            if (v2 <= t[l]) bst = min(bst, v2);
        }
    }
    if (s && r > 0) {
        bst = min(bst, rec(l, r - 1, k, 0) + d(l, r));
        bst = min(bst, rec(l, r - 1, k, 1) + d(r - 1, r));
        if (k) {
            int v1 = rec(l, r - 1, k - 1, 0) + d(l, r);
            if (v1 <= t[r]) bst = min(bst, v1);
            int v2 = rec(l, r - 1, k - 1, 1) + d(r - 1, r);
            if (v2 <= t[r]) bst = min(bst, v2);
        }
    }
    return dp[l][r][k][s] = bst;
}

int32_t main() {
    boost();

    cin >> n >> L;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0][0] = dp[0][0][0][1] = dp[n + 1][0][0][0] = dp[n + 1][0][0][1] = 0;
    for (int l = 0; l <= n; l++) {
        int r = l - 1;
        if (r < 0) r = n;
        for (int k = 1; k <= n; k++) if (min(rec(l, r, k, 0),  rec(l, r, k, 1)) < 1e12) ans = max(ans, k);
    }
    printf("%lld\n", ans);

    return 0;
}

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