Submission #1285758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285758		Faisal_Saqib	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	1 ms	568 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=210;
ll x[N],t[N];
pair<ll,ll> dp[N][N][4];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,tl;
    cin>>n>>tl;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    x[n]=tl;
    for(int i=0;i<n;i++)
    {
        cin>>t[i];
    }
    for(int l=0;l<=n;l++)
    {
        for(int r=0;r+l<=n;r++)
        {
            dp[l][r][0]=dp[l][r][1]=dp[l][r][2]={-1e9,1e9};
        }
    }
    // dp[l][r][3] = {max taken, min time}
    dp[0][0][0]=dp[0][0][1]=dp[0][0][2]={0,0};
    for(int sm=0;sm<=n;sm++)
    {
        // for(int r=0;r+l<=n;r++)
        for(int l=0;l<=sm;l++)
        {
            int r=sm-l;
            
            // 0 mean at l 
            // 1 mean at 0 
            // 2 mean at r
            for(int er=0;er<2;er++)
            {
                ll tm=dp[l][r][0].second,tk=dp[l][r][0].first;
                if(l+r<n)
                {
                    dp[l+1][r][0]=max(dp[l+1][r][0],{tk+(t[n-l-1]>=-tm-(x[n-1-l]-x[n-l])),tm+(x[n-1-l]-x[n-l])});
                }
                if(l>0)
                    dp[l][r][1]=max(dp[l][r][1],{tk,tm-(tl-x[n-l])});

                tm=dp[l][r][2].second,tk=dp[l][r][2].first;
                if(l+r<n and r>0)
                {
                    // x[r-1] x[r]
                        dp[l][r+1][2]=max(dp[l][r+1][2],{tk+(t[r]>=-tm+(x[r]-x[r-1])),tm-(x[r]-x[r-1])});
                }
                if(r>0)
                    dp[l][r][1]=max(dp[l][r][1],{tk,tm-x[r-1]});
                tm=dp[l][r][1].second,tk=dp[l][r][1].first;
                // max {taken,-time}
                if(r+l<n)
                {
                    dp[l+1][r][0]=max(dp[l+1][r][0],{tk+(t[n-l-1]>=-tm+x[n-l-1]),tm-x[n-l-1]});
                    // cout<<l<<' '<<r<<' '<<tk<<' '<<tm<<' '<<t[r]<<' '<<-tm+x[r]<<endl;
                    dp[l][r+1][2]=max(dp[l][r+1][2],{tk+(t[r]>=-tm+x[r]),tm-x[r]});
                }
                if(l>0)
                {
                    dp[l][r][0]=max(dp[l][r][0],{tk,tm-(tl-x[n-l])});
                }
                if(r>0)
                {
                    dp[l][r][2]=max(dp[l][r][2],{tk,tm-x[r-1]});
                }
            }
            // cout<<"For "<<l<<' '<<r<<endl;
            // for(int j=0;j<3;j++)
            // {
            //     cout<<'\t'<<dp[l][r][j].first<<' '<<dp[l][r][j].second<<endl;
            // }

        }
    }
    ll ans=0;
    for(int l=0;l<=n;l++)
    {
        for(int j=0;j<3;j++)
            ans=max(ans,dp[l][n-l][j].first);
    }
    cout<<ans<<endl;
}

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