Submission #340677

#	Time	Username	Problem	Language	Result	Execution time	Memory
340677		ijxjdjd	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	71 ms	135276 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 205;
const ll INF = (ll)(1e18);

ll dp[MAXN][MAXN][MAXN][2];
bool vis[MAXN][MAXN][MAXN][2];
ll pref[MAXN];
ll suff[MAXN];
ll arr[MAXN];
ll T[MAXN];
int N;
ll calc(int pre, int suf, int tot, int k) {
    if (tot < 0 || pre < 0 || suf > N+2) {
        return INF;
    }
    if (vis[pre][suf][tot][k]){
        return dp[pre][suf][tot][k];
    }
    vis[pre][suf][tot][k] = true;
    if (k == 0 && pre != 0) {
        ll curSide = calc(pre-1, suf, tot-1, k);
        ll otherSide = calc(pre-1, suf, tot-1, k^1);
        ll none = min(calc(pre-1, suf, tot, k) + arr[pre], calc(pre-1, suf, tot, k^1) + suff[suf] + pref[pre]);
        if (curSide + arr[pre] <= T[pre]) {
            none = min(none, curSide + arr[pre]);
        }
        if (otherSide + suff[suf] + pref[pre] <= T[pre]) {
            none = min(none, otherSide + suff[suf] + pref[pre]);
        }
        return dp[pre][suf][tot][k] = none;
    }
    else if (k == 1 && suf != N+2) {
        ll curSide = calc(pre, suf+1, tot-1, k);
        ll otherSide = calc(pre, suf+1, tot-1, k^1);
        ll none = min(calc(pre, suf+1, tot, k) + arr[suf], calc(pre, suf+1, tot, k^1) + suff[suf] + pref[pre]);
        if (curSide + arr[suf] <= T[suf-1]) {
            none = min(none, curSide + arr[suf]);
        }
        if (otherSide + suff[suf] + pref[pre] <= T[suf-1]) {
            none = min(none, otherSide + suff[suf] + pref[pre]);
        }
        return dp[pre][suf][tot][k] = none;
    }
    return dp[pre][suf][tot][k] = INF;
}
int main() {
    int L;
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        cin >> arr[i+1];
    }
    arr[N+1] = L - arr[N];
    for (int i = N; i >= 1; i--) {
        arr[i] -= arr[i-1];
    }
    for (int i = 0; i < N; i++) {
        cin >> T[i+1];
    }
    for (int i = 1; i <= N+2; i++) {
        pref[i] = pref[i-1] + arr[i];
    }
    for (int i = N+2; i >= 0; i--) {
        suff[i] = arr[i] + suff[i+1];
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            for (int k = 0; k < MAXN; k++) {
                dp[i][j][k][0] = INF;
                dp[i][j][k][1] = INF;
            }
        }
    }
    dp[0][N+2][0][0] = 0;
    dp[0][N+2][0][1] = 0;
    vis[0][N+2][0][0] = true;
    vis[0][N+2][0][1] = true;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k <= N; k++) {
            if (min(calc(i, i+2, k, 0), calc(i, i+2, k, 1)) < INF) {
                ans = max(ans, k);
            }
        }
    }
    cout << ans << '\n';
}

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