# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
224051 | jamielim | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 5 ms | 384 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |