제출 #1341897

#제출 시각아이디문제언어결과실행 시간메모리
1341897DangerNoodle7591Collecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
1 ms580 KiB
#include <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 205
#define pb push_back
#define int long long int
#define s second
#define big 1000000000000

int arr[N][2],ters[N][2];
int n,k;
int dp[N][N][N][2];//clockwise ,anticlockwise, kaç_aldım, nerdeydim=min tim



signed main(){
    lalala;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i][0];
    for(int i=1;i<=n;i++)cin>>arr[i][1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                dp[i][j][k][0]=big;
                dp[i][j][k][1]=big;
            }
        }
    }
    dp[0][0][0][1]=0;
    dp[0][0][0][0]=0;
    arr[n+1][0]=k;
    //kac==0;precomputeÜ
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            int b=n-j-1;
            if(i==0&&j==0)continue;
            dp[i][j][0][1]=k-arr[b][0]+2*arr[i][0];
            dp[i][j][0][0]=(k-arr[b][0])*2+arr[i][0];

        }
    }


    for(int co=0;co<=n;co++){
        for(int anti=0;anti<=n;anti++){
            if(anti+co>n)break;
            for(int kac=1;kac<=co+anti;kac++){
                if(co==0&&anti==0)break;
                int yer=n-anti+1;
                //cout<<co<<" "<<anti<<" "<<kac<<" "<<yer<<endl;
                if(co){
                    //0 dayim
                    int uzak=(arr[co][0]-arr[co-1][0]);
                    dp[co][anti][kac][0]=dp[co-1][anti][kac][0]+uzak;
                    int a=dp[co-1][anti][kac-1][0]+uzak;
                    if(a<=arr[co][1])dp[co][anti][kac][0]=min(dp[co][anti][kac][0],a);

                    uzak=(arr[co][0]+k-arr[yer][0]);
                    dp[co][anti][kac][0]=min(dp[co][anti][kac][0],  dp[co-1][anti][kac][1]+uzak);
                    a=dp[co-1][anti][kac-1][1]+uzak;
                    if(a<=arr[co][1])dp[co][anti][kac][0]=min(dp[co][anti][kac][0],a);
                    
                }
                if(yer<=n){
                    //1deyim
                    int uzak=abs(arr[yer][0]-arr[yer+1][0]);
                    dp[co][anti][kac][1]=dp[co][anti-1][kac][1]+uzak;
                    int a=dp[co][anti-1][kac-1][1]+uzak;
                    if(a<=arr[yer][1])dp[co][anti][kac][1]=min(dp[co][anti][kac][1],a);

                    uzak=(arr[co][0]+k-arr[yer][0]);
                    dp[co][anti][kac][1]=min(dp[co][anti][kac][1],  dp[co][anti-1][kac][0]+uzak);
                    a=dp[co][anti-1][kac-1][0]+uzak;
                    if(a<=arr[yer][1])dp[co][anti][kac][0]=min(dp[co][anti][kac][0],a);
                    //cout<<dp[co][anti][kac][1]<<" ! "<<uzak<<endl<<endl;
                }

            }
        }
    }

    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(dp[i][j][k][0]<big)ans=max(ans,k);
                if(dp[i][j][k][1]<big)ans=max(ans,k);
            }
        }
    }cout<<ans<<endl;


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...