Submission #211507

#	Time	Username	Problem	Language	Result	Execution time	Memory
211507		brcode	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	212 ms	267256 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 way){
    if(way == 0){
        if(arr[to]>=arr[from]){
            return arr[to]-arr[from];
        }
        return l-arr[from]+arr[to];
    }else{
        if(arr[from]>=arr[to]){
            return arr[from]-arr[to];
        }
        return arr[from]+l-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];
    }
    
    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));
                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);
               // cout<<currl<<" "<<currr<<endl;
                
                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+1][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<<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));
                }
            }
        }
    }
    cout<<ans<<endl;   
}

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