Submission #758236

#	Time	Username	Problem	Language	Result	Execution time	Memory
758236		xyzxyz	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	1022 ms	455804 KiB

ho_t3

#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, laenge; cin >> n >> laenge;
    vector<int> wo(n+2, 0), zeit(n+2, 0);
    for(int i=1; i<=n; i++) cin >> wo[i];
    for(int i=1; i<=n; i++) cin >> zeit[i];
    wo[n+1] = laenge;
    zeit[n+1] = 0;
    vector<vector<vector<vector<int>>>> dp(n+2, vector<vector<vector<int>>>(n+2, vector<vector<int>>(n+2, vector<int>(2, 1e18))));
    dp[n+1][0][0][1] = 0;
    dp[n+1][0][0][0] = 0;
    int res = 0;
    for(int c=0; c<n; c++){//Anz Marken
        for(int l=n+1; l>0; l--){//linkes Ende
            for(int r=0; r<l; r++){//rechtes Ende
                if(dp[l][r][c][0]!=1e18){//sind am linken Ende
                    //ans rechte Ende laufen
                    if(r+1!=l){
                        int dist = wo[r+1]+laenge-wo[l];
                        if(dp[l][r][c][0]+dist<=zeit[r+1]){
                            dp[l][r+1][c+1][1] = min(dp[l][r][c][0] + dist, dp[l][r+1][c+1][1]);
                            res = max(res, c+1);
                        }else dp[l][r+1][c][1] = min(dp[l][r+1][c][1], dp[l][r][c][0] + dist);
                    }
                    //ans neue linke Ende laufen
                    if(l-1!=r){
                        int dist = wo[l]-wo[l-1];
                        if(dp[l][r][c][0]+dist<=zeit[l-1]){
                            dp[l-1][r][c+1][0] = min(dp[l-1][r][c+1][0], dp[l][r][c][0] + dist);
                            res = max(res, c+1);
                        }else dp[l-1][r][c][0] = min(dp[l-1][r][c][0], dp[l][r][c][0] + dist);
                    }
                    
                }
                if(dp[l][r][c][1]!=1e18){//sind am rechten Ende
                    //ans linke Ende laufen
                    int dist = wo[r]+laenge-wo[l-1];
                    if(l-1!=r){
                        if(dp[l][r][c][1]+dist<=zeit[l-1]){
                            dp[l-1][r][c+1][0] = min(dp[l-1][r][c+1][0], dp[l][r][c][1] + dist);
                            res = max(res, c+1);
                        }else dp[l-1][r][c][0] = min(dp[l-1][r][c][0], dp[l][r][c][1] + dist);
                    }
                    //ans neue rechte Ende laufen
                    dist = wo[r+1]-wo[r];
                    if(r+1!=l){
                        if(dp[l][r][c][1]+dist<=zeit[r+1]){
                            dp[l][r+1][c+1][1] = min(dp[l][r+1][c+1][1], dp[l][r][c][1] + dist);
                            res = max(res, c+1);
                        }else dp[l][r+1][c][1] = min(dp[l][r+1][c][1], dp[l][r][c][1] + dist);
                    }
                }
            }
        }
    }
    cout << res;
    return 0;
}

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