Submission #224051

#TimeUsernameProblemLanguageResultExecution timeMemory
224051jamielimCollecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
5 ms384 KiB
#include <bits/stdc++.h> using namespace std; const long long INF=1012345678012345LL; int main(){ int n;long long l; scanf("%d%lld",&n,&l); long long x[n+2],t[n+2]; x[0]=0;x[n+1]=l;t[0]=t[n+1]=INF; for(int i=1;i<=n;i++)scanf("%lld",&x[i]); for(int i=1;i<=n;i++)scanf("%lld",&t[i]); long long dp[n+2][n+2][n+1][2]; //time for(int i=0;i<n+2;i++){ for(int j=0;j<n+2;j++){ for(int k=0;k<=n;k++)dp[i][j][k][0]=dp[i][j][k][1]=INF; } } dp[0][n+1][0][0]=0;dp[0][n+1][0][1]=0; for(int k=0;k<=n;k++){ for(int i=0;i<=n;i++){ for(int j=n+1;j>=1;j--){ if(i>0){ if(k>0){ if(dp[i-1][j][k-1][0]+x[i]-x[i-1]<=t[i]) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][0]+x[i]-x[i-1]); if(dp[i-1][j][k-1][1]+l-(x[j]-x[i])<=t[i]) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+l-(x[j]-x[i])); } dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+x[i]-x[i-1]); dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+l-(x[j]-x[i])); } if(j<n+1){ if(k>0){ if(dp[i][j+1][k-1][0]+l-(x[j]-x[i])<=t[j]) dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][0]+l-(x[j]-x[i])); if(dp[i][j+1][k-1][1]+x[j+1]-x[j]<=t[j]) dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][1]+x[j+1]-x[j]); } dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][0]+l-(x[j]-x[i])); dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][1]+x[j+1]-x[j]); } //printf("%lld %lld ",dp[i][j][0],dp[i][j][1]); dp[i][j][k][0]=min(dp[i][j][k][0],dp[i][j][k][1]+l-(x[j]-x[i])); dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j][k][0]+l-(x[j]-x[i])); //printf("%lld %lld\n",dp[i][j][0],dp[i][j][1]); } //printf("\n"); } } int ans=0; for(int i=0;i<n+2;i++){ for(int j=0;j<n+2;j++){ for(int k=0;k<=n;k++){ if(dp[i][j][k][0]<INF||dp[i][j][k][1]<INF){ ans=max(ans,k); } } } } //for(int i=0;i<n+2;i++){for(int j=0;j<n+2;j++)printf("%lld ",dp[i][j][0]);printf("\n");} //for(int i=0;i<n+2;i++){for(int j=0;j<n+2;j++)printf("%lld ",dp[i][j][1]);printf("\n");} printf("%d",ans); }

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:11:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
                       ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
                       ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...