제출 #702608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702608		1075508020060209tc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	180 ms	298340 KiB

ho_t3

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second

int n;int L;
int xar[2010];
int tar[2010];
int dpl[300][300][300];
int dpr[300][300][300];
signed main(){

    cin>>n>>L;
    for(int i=1;i<=n;i++){
        cin>>xar[i];
    }xar[n+1]=L;
    for(int i=1;i<=n;i++){
        cin>>tar[i];
    }
    for(int i=0;i<=250;i++){
        for(int j=0;j<=250;j++){
            for(int k=0;k<=250;k++){
                dpl[i][j][k]=1e16;
                dpr[i][j][k]=1e16;
            }
        }
    }

    dpl[0][0][0]=0;
    dpr[0][0][0]=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(i+j>=n){continue;}
                if(dpr[i][j][k]<1e16){
                if(tar[j+1]>=dpr[i][j][k]+xar[j+1]-xar[j]){
                    dpr[i][j+1][k+1]=min(dpr[i][j+1][k+1],dpr[i][j][k]+xar[j+1]-xar[j]);
                }else{
                    dpr[i][j+1][k]=min(dpr[i][j+1][k],dpr[i][j][k]+xar[j+1]-xar[j]);
                }

                if(tar[n-(i+1)+1]>=dpr[i][j][k]+xar[j]+L-xar[n-(i+1)+1]){
                    dpl[i+1][j][k+1]=min(dpl[i+1][j][k+1],dpr[i][j][k]+xar[j]+L-xar[n-(i+1)+1]);
                }else{
                    dpl[i+1][j][k]=min(dpl[i+1][j][k],dpr[i][j][k]+xar[j]+L-xar[n-(i+1)+1]);
                }
                }
                if(dpl[i][j][k]<1e16){
                if(tar[j+1]>=dpl[i][j][k]+L-xar[n-i+1]+xar[j+1]){
                    dpr[i][j+1][k+1]=min(dpr[i][j+1][k+1],dpl[i][j][k]+L-xar[n-i+1]+xar[j+1]);
                }else{
                    dpr[i][j+1][k]=min(dpr[i][j+1][k],dpl[i][j][k]+L-xar[n-i+1]+xar[j+1]);
                }

                if(tar[n-(i+1)+1]>=dpl[i][j][k]+xar[n-i+1]-xar[n-(i+1)+1]){
                    dpl[i+1][j][k+1]=min(dpl[i+1][j][k+1],dpl[i][j][k]+xar[n-i+1]-xar[n-(i+1)+1]);
                }else{
                    dpl[i+1][j][k]=min(dpl[i+1][j][k],dpl[i][j][k]+xar[n-i+1]-xar[n-(i+1)+1]);
                }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int k=0;k<=n;k++){
            if(dpl[i][n-i][k]<1e16){
                ans=max(ans,k);
            }
            if(dpr[i][n-i][k]<1e16){
                ans=max(ans,k);
            }
            //cout<<i<<" "<<k<<" "<<dpl[i][n-i][k]<<"\n";
        }
    }


    cout<<ans<<endl;

    int a;int b;int c;int d;
    while(cin>>a){
        cin>>b>>c>>d;
        if(a==0){
            cout<<dpl[b][c][d]<<endl;
        }else{
            cout<<dpr[b][c][d]<<endl;
        }
    }

}

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