제출 #1296227

#제출 시각아이디문제언어결과실행 시간메모리
1296227fairkrashCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
411 ms448916 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll INF = 1e18;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, dist;
    cin >> n >> dist;
    vector<ll> s(n), z(n);
    ll las = 0;
    for (ll i = 0; i < n; i++) {
        cin >> s[i];
        las = s[i];
    }
    vector<ll> v2(n);
    v2[0] = dist - las;
    for (ll i = 1; i < n; i++) {
        v2[i] = s[n - i] - s[n - i - 1];
    }
    for (ll i = n - 1; i >= 1; i--) {
        s[i] = s[i] - s[i - 1];
    }
    for (ll i = 0; i < n; i++) {
        cin >> z[i];
    }
    auto v1 = s;
    vector<ll> sum_l(n + 1);
    vector<ll> sum_r(n + 1);
    vector<ll> time_l(n);
    vector<ll> time_r(n);
    for (ll i = 0; i < n; i++) {
        sum_l[i + 1] = sum_l[i] + v1[i];
    }
    for (ll i = 0; i < n; i++) {
        time_l[i] = z[i];
    }
    time_r = time_l;
    reverse(time_r.begin(), time_r.end());
    for (ll i = 0; i < n; i++) {
        sum_r[i + 1] = sum_r[i] + v2[i];
    }
    vector<vector<vector<vector<ll>>>> dp(n + 1, vector<vector<vector<ll>>>(n + 1, vector<vector<ll>>(n + 1,
                                                                                                      vector<ll>(2,
                                                                                                                 INF))));
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j <= i; j++) {
            for (ll e = 0; e <= i; e++) {
                ll l = j;
                ll r = i - j;
                ll tm = dp[l][r][e][0];
                ll all = sum_l[l] + sum_r[r];
                dp[l + 1][r][e][0] = min(dp[l + 1][r][e][0], tm + v1[l]);
                if (tm + v1[l] <= time_l[l]) {
                    dp[l + 1][r][e + 1][0] = min(dp[l + 1][r][e + 1][0], tm + v1[l]);
                }
                dp[l + 1][r][e][1] = min(dp[l + 1][r][e][1], tm + v1[l] + v1[l] + all);
                if (tm + v1[l] <= time_l[l]) {
                    dp[l + 1][r][e + 1][1] = min(dp[l + 1][r][e + 1][1], tm + v1[l] + v1[l] + all);
                }
                tm = dp[l][r][e][1];
                dp[l][r + 1][e][1] = min(dp[l][r + 1][e][1], tm + v2[r]);
                if (tm + v2[r] <= time_r[r]) {
                    dp[l][r + 1][e + 1][1] = min(dp[l][r + 1][e + 1][1], tm + v2[r]);
                }
                dp[l][r + 1][e][0] = min(dp[l][r + 1][e][0], tm + v2[r] + v2[r] + all);
                if (tm + v2[r] <= time_r[r]) {
                    dp[l][r + 1][e + 1][0] = min(dp[l][r + 1][e + 1][0], tm + v2[r] + v2[r] + all);
                }
            }
        }
    }
    for (ll i = 0; i <= n; i++) {
        for (ll j = 0; j <= i; j++) {
            for (ll e = 0; e <= i; e++) {
                ll l = j;
                ll r = i - j;
                if (dp[l][r][e][0] < INF) {
                    ans = max(ans, e);
                }
                if (dp[l][r][e][1] < INF) {
                    ans = max(ans, e);
                }
            }
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...