Submission #702574

#	Time	Username	Problem	Language	Result	Execution time	Memory
702574		guagua0407	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	132 ms	129492 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define all(x) x.begin(),x.end()

const int mxn=205;
ll dp[mxn][mxn][mxn][2];
ll X[mxn];
ll T[mxn];
int n;
ll L;

ll dist(int a,int b){
    if(a<=b) return X[b]-X[a];
    return X[b]+L-X[a];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>X[i];
    }
    for(int i=0;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++){
                for(int l=0;l<2;l++){
                    dp[i][j][k][l]=(ll)1e18;
                }
            }
        }
    }
    if(X[0]<=T[0]) dp[0][0][1][0]=dp[0][0][1][1]=X[0];
    else dp[0][0][0][0]=dp[0][0][0][1]=X[0];
    if(L-X[n-1]<=T[n-1]) dp[n-1][n-1][1][0]=dp[n-1][n-1][1][1]=L-X[n-1];
    else dp[n-1][n-1][0][0]=dp[n-1][n-1][0][1]=L-X[n-1];
    for(int gap=1;gap<n;gap++){
        for(int i=0;i<n;i++){
            int j=(i+gap)%n;
            dp[i][j][0][0]=min(dp[i][j][0][0],dp[(i+1)%n][j][0][0]+dist(i,(i+1)%n));
            dp[i][j][0][1]=min(dp[i][j][0][1],dp[i][(j-1+n)%n][0][1]+dist((j-1+n)%n,j));
            for(int k=1;k<=n;k++){
                if(dp[(i+1)%n][j][k-1][0]+dist(i,(i+1)%n)<=T[i]){
                    dp[i][j][k][0]=min(dp[i][j][k][0],dp[(i+1)%n][j][k-1][0]+dist(i,(i+1)%n));
                }
                else{
                    dp[i][j][k][0]=min(dp[i][j][k][0],dp[(i+1)%n][j][k][0]+dist(i,(i+1)%n));
                }
                if(dp[i][(j-1+n)%n][k-1][1]+dist((j-1+n)%n,j)<=T[j]){
                    dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][(j-1+n)%n][k-1][1]+dist((j-1+n)%n,j));
                }
                else{
                    dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][(j-1+n)%n][k][1]+dist((j-1+n)%n,j));
                }
            }
            for(int k=0;k<=n;k++){
                dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j][k][1]+dist(i,j));
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j][k][0]+dist(i,j));
            }
        }
    }
    for(int k=n;k>=0;k--){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int l=0;l<2;l++){
                    if(dp[i][j][k][l]<(ll)1e18){
                        cout<<k;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

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