Submission #758218

#	Time	Username	Problem	Language	Result	Execution time	Memory
758218		xyzxyz	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	450 ms	328056 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;
    pair<int,int> punkte;
    int res = 0;
    for(int c=0; c<n; c++){//Anz Marken
        for(int l=n+1; l>0; l--){//linkes Ende -> wo[l]
            for(int r=0; r<l; r++){//rechtes Ende
                if(dp[l][r][c][0]!=1e18){//sind am linken Ende
                    //ans rechte Ende laufen
                    int tmp = r+1;
                    if(tmp!=l){
                        int dist = wo[tmp]+laenge-wo[l];
                        if(dp[l][r][c][0]+dist<=zeit[tmp] && tmp!=0 && tmp!=laenge){
                            dp[l][tmp][c+1][1] = dp[l][r][c][0] + dist;
                            if(c+1>res) punkte = {l, tmp};
                            res = max(res, c+1);
                        }else dp[l][tmp][c][1] = dp[l][r][c][0] + dist;
                    }
                    //ans neue linke Ende laufen
                    tmp = l-1;
                    if(tmp!=r){
                        int dist = wo[l]-wo[tmp];
                        if(dp[l][r][c][0]+dist<=zeit[tmp] && tmp!=0 && tmp!=laenge){
                            dp[tmp][r][c+1][0] = dp[l][r][c][0] + dist;
                            if(c+1>res) punkte = {tmp, r};
                            res = max(res, c+1);
                        }else dp[tmp][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 tmp = l-1;
                    int dist = wo[r]+laenge-wo[tmp];
                    if(tmp!=r){
                        if(dp[l][r][c][1]+dist<=zeit[tmp] && tmp!=0 && tmp!=laenge){
                            dp[tmp][r][c+1][0] = dp[l][r][c][1] + dist;
                            if(c+1>res) punkte = {tmp, r};
                            res = max(res, c+1);
                        }else dp[tmp][r][c][0] = dp[l][r][c][1] + dist;
                    }
                    //ans neue rechte Ende laufen
                    tmp = r+1;
                    dist = wo[r+1]-wo[r];
                    if(tmp!=l){
                        if(dp[l][r][c][1]+dist<=zeit[tmp] && tmp!=0 && tmp!=laenge){
                            dp[l][tmp][c+1][1] = dp[l][r][c][1] + dist;
                            if(c+1>res) punkte = {l, tmp};
                            res = max(res, c+1);
                        }else dp[l][tmp][c][1] = dp[l][r][c][1] + dist;
                    }
                }
            }
        }
    }
    cout << res;
    return 0;
}

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