# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
959251 | AndreiBOTO | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 241 ms | 445008 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>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
///What a day...
///You look lonely, I can fix that
const long long INF=1e13;
const int NMAX=305;
#define int long long
int dp[NMAX][NMAX][NMAX][2]; ///minimum time -> clock, counter-clock, answer, direction (0->clock, 1->counter-clock)
int x[NMAX];
int t[NMAX];
int l;
int get_dist(int a,int b)
{
///I got guns in my head and they won't go,
///Spirits in my head and they won't go...
if(a==b)
return 0;
else
{
if(a>b)
swap(a,b);
return min(x[b]-x[a],l-x[b]+x[a]);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,i,j,k,st,dr,ans,best=0;
cin>>n>>l;
for(i=1;i<=n;i++)
cin>>x[i];
x[0]=0;
x[n+1]=l;
for(i=1;i<=n;i++)
cin>>t[i];
t[0]=-1;
t[n+1]=-1;
/*for(i=0;i<=n+1;i++)
for(j=0;j<=n+1;j++)
for(k=0;k<=n+1;k++)
dp[i][j][k][0]=dp[i][j][k][1]=INF;*/
memset(dp,63,sizeof(dp));
dp[0][0][0][0]=dp[0][0][0][1]=0;
for(st=0;st<=n;st++)
{
for(dr=0;dr<=n;dr++)
{
if(st+dr>n)
break;
for(ans=0;ans<=n;ans++)
{
if(min(dp[st][dr][ans][0],dp[st][dr][ans][1])<INF)
best=max(best,ans);
if(st+1<=n)
{
long long auxy=dp[st][dr][ans][1]+get_dist(n+1-dr,st+1);
auxy=min(auxy,dp[st][dr][ans][0]+get_dist(st,st+1));
if(auxy<=t[st+1])
dp[st+1][dr][ans+1][0]=min(dp[st+1][dr][ans+1][0],auxy);
else
dp[st+1][dr][ans][0]=min(dp[st+1][dr][ans][0],auxy);
}
if(dr+1<=n)
{
long long auxy=dp[st][dr][ans][1]+get_dist(n+1-dr,n+1-dr-1);
auxy=min(auxy,dp[st][dr][ans][0]+get_dist(st,n+1-dr-1));
if(auxy<=t[n+1-dr-1])
dp[st][dr+1][ans+1][1]=min(dp[st][dr+1][ans+1][1],auxy);
else
dp[st][dr+1][ans][1]=min(dp[st][dr+1][ans][1],auxy);
}
}
}
}
cout<<best<<"\n";
return 0;
}
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... |