Submission #959269

#	Time	Username	Problem	Language	Result	Execution time	Memory
959269		AndreiBOTO	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	101 ms	241244 KiB

ho_t3

#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]=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(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])
                    {
                        if(ans+1>n)
                            continue;
                        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])
                    {
                        if(ans+1>n)
                            continue;
                        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);
                }
            }
        }
    }
    for(ans=n;ans>=0;ans--)
    {
        for(st=0;st<=n;st++)
        {
            dr=n-st;
            if(dp[st][dr][ans][0]<INF || dp[st][dr][ans][1]<INF)
            {
                cout<<ans;
                exit(0);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

ho_t3.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      |

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75