Submission #1133251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133251		Unforgettablepl	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	167 ms	132348 KiB

ho_t3

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

#define int long long

const int INF = 1e10;


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,L;
    cin >> n >> L;
    vector<int> pos(n+2),tim(n+1);
    for(int i=1;i<=n;i++)cin>>pos[i];
    pos[n+1]=L;
    for(int i=1;i<=n;i++)cin>>tim[i];
    vector DP(n+1,vector(n+1,vector(2,vector(n+1,INF))));
    DP[0][0][0][0]=DP[0][0][1][0]=0;
    for(int l=0;l<=n;l++) {
        for(int r=0;r<=n-l;r++) {
            for(int score=0;score<=n;score++) {
                // End at L
                if(l) {
                    if(score and tim[l]>=DP[l-1][r][0][score-1]+pos[l]-pos[l-1]) {
                        DP[l][r][0][score]=DP[l-1][r][0][score-1]+pos[l]-pos[l-1];
                    } else {
                        DP[l][r][0][score]=DP[l-1][r][0][score]+pos[l]-pos[l-1];
                    }
                }
                // End at r
                if(r) {
                    if(score and tim[n+1-r]>=DP[l][r-1][1][score-1]+pos[n+2-r]-pos[n+1-r]) {
                        DP[l][r][1][score]=DP[l][r-1][1][score-1]+pos[n+2-r]-pos[n+1-r];
                    } else {
                        DP[l][r][1][score]=DP[l][r-1][1][score]+pos[n+2-r]-pos[n+1-r];
                    }
                }
                int dist = pos[l]+L-pos[n+1-r];
                DP[l][r][0][score]=min(DP[l][r][0][score],DP[l][r][1][score]+dist);
                DP[l][r][1][score]=min(DP[l][r][1][score],DP[l][r][0][score]+dist);
            }
        }
    }
    for(int x=n;x>=0;x--) {
        for(auto&i:DP) {
            for(auto&j:i) {
                for(auto&k:j) {
                    if(k[x]<INF){
                        cout<<x<<'\n';return 0;
                    }
                }
            }
        }
    }
    assert(false);
}

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