제출 #1353507

#제출 시각아이디문제언어결과실행 시간메모리
1353507guardianecCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
54 ms132068 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll INF = 1e18;

ll dp[207][207][207][2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n,l;
    cin >> n >> l;
    vector<ll> x(n+1),t(n+1);
    for (int i=1; i<=n; i++) {
        cin >> x[i];
    }

    for (int i=1; i<=n; i++) {
        cin >> t[i];
    }

    for (int i=0; i<=n; i++) {
        for (int j=0; j<=n; j++) {
            for (int k=0; k<=n; k++) dp[i][j][k][0] = dp[i][j][k][1] = INF;
        }
    }

    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    
    for (int s=0; s<n; s++) {
        for (int i=0; i<=s; i++) {
            ll j = s-i;
            for (int k=0; k<=s; k++) {
                if (dp[i][j][k][0]!=INF) {
                    ll t1 = dp[i][j][k][0]+(x[i+1]-x[i]);
                    ll k1 = k+(t1<=t[i+1] ? 1 : 0);
                    dp[i+1][j][k1][0] = min(dp[i+1][j][k1][0], t1);

                    t1 = dp[i][j][k][0]+(x[i]+(l-x[n-j]));
                    k1 = k+(t1<=t[n-j] ? 1 : 0);
                    dp[i][j+1][k1][1] = min(dp[i][j+1][k1][1], t1);
                }

                if (dp[i][j][k][1]!=INF) {
                    ll curr = (j==0 ? 0 : x[n-j+1]);
                    ll t1 = dp[i][j][k][1]+((j==0 ? x[i+1] : (l-curr+x[i+1])));
                    ll k1 = k+(t1<=t[i+1] ? 1 : 0);
                    dp[i+1][j][k1][0] = min(dp[i+1][j][k1][0], t1);

                    t1 = dp[i][j][k][1]+((j==0 ? l-x[n] : curr-x[n-j]));
                    k1 = k+(t1<=t[n-j] ? 1 : 0);
                    dp[i][j+1][k1][1] = min(dp[i][j+1][k1][1], t1);
                }
            }
        }
    }

    ll res = 0;
    for (int i=0; i<=n; i++) {
        for (int j=0; i+j<=n; j++) {
            for (ll k=0; k<=n; k++) {
                if (dp[i][j][k][0]!=INF || dp[i][j][k][1]!=INF) {
                    res = max(res, k);
                }
            }
        }
    }

    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...