제출 #211616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211616		brcode	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	328 ms	333304 KiB

ho_t3

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long n,l;
long long ans = 0;
const long long MAXN = 210;
long long dp[MAXN][MAXN][MAXN][5];
long long arr[MAXN];
long long t[MAXN];
long long check(long long x){
    x+=(n+1);
    x%=(n+1);
    return x;
}
long long dist(long long from,long long to,long long x){
     
        if(arr[to]>=arr[from]){
             x=arr[to]-arr[from];
        }
        return min(abs(arr[to]-arr[from]),l-abs(arr[from]-arr[to]));
   
    
    
}
int main(){
    cin>>n>>l;
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=n;j++){
            for(long long k=0;k<=n;k++){
                for(long long l=0;l<=4;l++){
                    dp[i][j][k][l] = 1e14;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(long long i=1;i<=n;i++){
        cin>>t[i];
    }
    t[0] = -1e9;
    for(long long i=0;i<=n;i++){
        for(long long len=0;len<=n;len++){
            for(long long l=0;l<=n;l++){
                
                long long r=check(l+len);
                if(len == 0 && l==0){
                    r=0;
                }else if(len == 0){
                    continue;
                }
                dp[i][l][r][0] = min(dp[i][l][r][0],dp[i][l][r][1]+dist(r,l,1));
                dp[i][l][r][1] = min(dp[i][l][r][1],dp[i][l][r][0]+dist(l,r,0));
                dp[i][l][r][0] = min(dp[i][l][r][0],dp[i][l][r][1]+dist(r,l,1));
                dp[i][l][r][1] = min(dp[i][l][r][1],dp[i][l][r][0]+dist(l,r,0));
                long long currl = dp[i][l][r][0];
                long long currr = dp[i][l][r][1];
                
              //  cout<<len<<" "<<l<<" "<<r<<endl;
                if(currl>=1e14 && currr >=1e14){
                    continue;
                }

                ans = max(ans,i);
                if(i==1){
                  //  cout<<l<<" "<<r<<" "<<currl<<" "<<currr<<endl;
                }
               // cout<<currl<<" "<<currr<<endl;
                //int nxt = min(dist(l,check(r+1),0))
                if(currl+dist(l,check(r+1),0)<=t[check(r+1)]){
                    dp[i+1][l][check(r+1)][1] = min(dp[i+1][l][check(r+1)][1],currl+dist(l,check(r+1),0));
                    
                }else{
                    dp[i][l][check(r+1)][1] = min(dp[i][l][check(r+1)][1],currl+dist(l,check(r+1),0));
                }
                
                if(currr+dist(r,check(r+1),0)<=t[check(r+1)]){
                    dp[i+1][l][check(r+1)][1] = min(dp[i+1][l][check(r+1)][1],currr+dist(r,check(r+1),0)); 
                }else{
                    dp[i][l][check(r+1)][1] = min(dp[i][l][check(r+1)][1],currr+dist(r,check(r+1),0));
                }
                
                if(currl+dist(l,check(l-1),1)<=t[check(l-1)]){
                    dp[i+1][check(l-1)][r][0]=min(dp[i+1][check(l-1)][r][0],currl+dist(l,check(l-1),1));
                    //cout<<i+1<<" "<<check(l-1)<<" "<<r<<endl;
                }else{
                    dp[i][check(l-1)][r][0]= min(dp[i][check(l-1)][r][0],currl+dist(l,check(l-1),1));
                }
                
                if(currr+dist(r,check(l-1),1)<=t[check(l-1)]){
                    dp[i+1][check(l-1)][r][0] = min(dp[i+1][check(l-1)][r][0],currr+dist(r,check(l-1),1));
                   // cout<<i+1<<endl;
                   // cout<<check(l-1)<<" "<<r<<" "<<dp[i+1][check(l-1)][r][0]<<endl;
                }else{
                    dp[i][check(l-1)][r][0] = min(dp[i][check(l-1)][r][0],currr+dist(r,check(l-1),1));
                }
            }
        }
    }
   for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                    if(dp[i][j][k][0]!=1e14||dp[i][j][k][1]!=1e14){
                       // cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k][0]<<" "<<dp[i][j][k][1]<<endl;;
                    }
                
            }
        }
    }
    cout<<ans<<endl;   
}

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