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=1e18;
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)
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[n+1]=l;
for(i=1;i<=n;i++)
cin>>t[i];
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;
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);
else
continue;
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);
best=max(best,ans+1);
}
else
dp[st+1][dr][ans][0]=min(dp[st+1][dr][ans][0],auxy);
}
if(dr+1<=n)
{
if(n+1-dr-1==0 || n+1-dr-1==n+1)
continue;
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);
best=max(best,ans+1);
}
else
dp[st][dr+1][ans][1]=min(dp[st][dr+1][ans][1],auxy);
}
}
}
}
cout<<best<<"\n";
return 0;
}
Compilation message (stderr)
ho_t3.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
3 | #pragma optimize GCC ("Ofast")
|
# | 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... |