Submission #548487

#	Time	Username	Problem	Language	Result	Execution time	Memory
548487		krit3379	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	126 ms	132852 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[n-i+1]=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][0][0]=0;
    //dp[][i][j][k] collect i stamp at j-th left and k-th right
    //dp[0]->left dp[1]->right
    for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=n;k++){
        if(j+k>n)continue;
        if(j)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)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(i&&j&&min(dp[0][i-1][j-1][k]+rev[j]-rev[j-1],dp[1][i-1][j-1][k]+rev[j]+x[k])<=t[n-j+1])dp[0][i][j][k]=min({dp[0][i][j][k],dp[0][i-1][j-1][k]+rev[j]-rev[j-1],dp[1][i-1][j-1][k]+rev[j]+x[k]});
        if(i&&k&&min(dp[1][i-1][j][k-1]+x[k]-x[k-1],dp[0][i-1][j][k-1]+rev[j]+x[k])<=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],dp[0][i-1][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[n-i+1]=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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75