Submission #548481

#	Time	Username	Problem	Language	Result	Execution time	Memory
548481		krit3379	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	980 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define N 205

int x[N],rev[N],t[N],ans;
long long dp[2][N][N][N];

int main(){
    int n,m,l,i,j,k;
    scanf("%d %d",&n,&l);
    for(i=1;i<=n;i++)scanf("%d",&x[i]),rev[i]=l-x[i];
    for(i=1;i<=n;i++)scanf("%d",&t[i]);
    for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++)for(k=0;k<=n+1;k++)dp[0][i][j][k]=dp[1][i][j][k]=1e18;
    dp[1][0][0][0]=dp[0][0][n+1][0]=0;
    
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            if(i&&j&&dp[1][i-1][0][j-1]+x[j]-x[j-1]<=t[j]){
                dp[1][i][0][j]=min(dp[1][i][0][j],dp[1][i-1][0][j-1]+x[j]-x[j-1]);
            }
            if(j)dp[1][i][0][j]=min(dp[1][i][0][j],dp[1][i][0][j-1]+x[j]-x[j-1]);
        }
    }
    
    for(i=0;i<=n;i++){
        for(j=n+1;j>0;j--){
            if(i&&j<=n&&dp[0][i-1][j+1][0]+rev[j]-rev[j+1]<=t[j]){
                dp[0][i][j][0]=min(dp[0][i][j][0],dp[0][i-1][j+1][0]+rev[j]-rev[j+1]);
            }
            if(j<=n)dp[0][i][j][0]=min(dp[0][i][j][0],dp[0][i][j+1][0]+rev[j]-rev[j+1]);
        }
    }
    for(i=0;i<=n;i++){
        for(j=n+1;j>=0;j--){
            for(k=0;k<=n+1;k++){
                if(i){
                    if(j&&j<=n&&dp[0][i-1][j+1][k]+rev[j]-rev[j+1]<=t[j])dp[0][i][j][k]=min(dp[0][i][j][k],dp[0][i-1][j+1][k]+rev[j]-rev[j+1]);
                    if(j&&j<=n&&dp[1][i-1][j+1][k]+rev[j]+x[k]<=t[j])dp[0][i][j][k]=min(dp[0][i][j][k],dp[1][i-1][j+1][k]+rev[j]+x[k]);
                    if(k&&k<=n&&dp[1][i-1][j][k-1]+x[k]-x[k-1]<=t[k])dp[1][i][j][k]=min(dp[1][i][j][k],dp[1][i-1][j][k-1]+x[k]-x[k-1]);
                    if(k&&k<=n&&dp[0][i-1][j][k-1]+x[k]+rev[j]<=t[k])dp[1][i][j][k]=min(dp[1][i][j][k],dp[0][i-1][j][k-1]+x[k]+rev[j]);
                }
                if(j&&j<=n)dp[0][i][j][k]=min({dp[0][i][j][k],dp[0][i][j+1][k]+rev[j]-rev[j+1],dp[1][i][j+1][k]+rev[j]+x[k]});
                if(k&&k<=n)dp[1][i][j][k]=min({dp[1][i][j][k],dp[1][i][j][k-1]+x[k]-x[k-1],dp[0][i][j][k-1]+rev[j]+x[k]});
                if(dp[0][i][j][k]<1e18||dp[1][i][j][k]<1e18)ans=max(ans,i);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:9:11: warning: unused variable 'm' [-Wunused-variable]
    9 |     int n,m,l,i,j,k;
      |           ^
ho_t3.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:11:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for(i=1;i<=n;i++)scanf("%d",&x[i]),rev[i]=l-x[i];
      |                      ~~~~~^~~~~~~~~~~~
ho_t3.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(i=1;i<=n;i++)scanf("%d",&t[i]);
      |                      ~~~~~^~~~~~~~~~~~

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