Submission #1285832

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

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=210;
ll x[N],tme[N];
ll dp[N][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>>tme[i];
    }
    // dp[l][r][taken][0,1,2] = min time
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                for(auto p:{0,1,2})
                    dp[i][j][k][p]=1e18;
            }
        }
    }
    dp[0][0][0][0]=0;
    for(int sm=0;sm<=n;sm++)
    {
        for(int l=0;l<=sm;l++)
        {
            int r=sm-l;
            for(int t=0;t<=sm;t++)
            {
                for(int typ=0;typ<2;typ++)
                {
                    ll tm=dp[l][r][t][0];
                    if(l>0)
                        dp[l][r][t][1]=min(dp[l][r][t][1],tm+(tl-x[n-l]));
                    if(l+r<n)
                        dp[l+1][r][t][0]=min(dp[l+1][r][t][0],tm+(x[n-l]-x[n-l-1]));
                    if(l+r<n and (tm+(x[n-l]-x[n-l-1]))<=tme[n-l-1])
                    {
                        dp[l+1][r][t+1][0]=min(dp[l+1][r][t+1][0],tm+(x[n-l]-x[n-l-1]));
                    }
                    
                    tm=dp[l][r][t][2];
                    if(r>0)
                        dp[l][r][t][1]=min(dp[l][r][t][1],tm+x[r-1]);
                    if(l+r<n and r==0)
                    {
                        dp[l][r+1][t][2]=min(dp[l][r+1][t][2],tm+x[0]);
                        tm+=x[0];
                    }
                    else if(l+r<n and r>0) // r>0
                    {
                        dp[l][r+1][t][2]=min(dp[l][r+1][t][2],tm+(x[r]-x[r-1]));
                        tm+=(x[r]-x[r-1]);
                    }
                    else{
                        tm=1e18;
                    }
                    // cout<<"Update "<<l<<' '<<r<<' '<<t<<' '<<2<<' '<<tm<<' '<<tme[r]<<endl;
                    if(tm<=tme[r])
                    {
                        dp[l][r+1][t+1][0]=min(dp[l][r+1][t+1][0],tm);
                    }
                    
                    // dp[l][r][t][1] -> dp[l+1][r][t][1]
                    tm=dp[l][r][t][1];
                    if(l+r<n)
                    {
                        dp[l+1][r][t][0]=min(dp[l+1][r][t][0],tm+(x[n-l]-x[n-1-l]));
                        if(tm+(x[n-l]-x[n-1-l])<=tme[n-1-l])
                            dp[l+1][r][t+1][0]=min(dp[l+1][r][t+1][0],tm+(x[n-l]-x[n-1-l]));

                        
                        if(r==0)
                        {
                            dp[l][r+1][t][2]=min(dp[l][r+1][t][2],tm+x[0]);
                            if((tm+x[0])<=tme[r])
                            {
                                dp[l][r+1][t+1][2]=min(dp[l][r+1][t+1][2],tm+x[0]);
                            }
                        }
                        else{
                            dp[l][r+1][t][2]=min(dp[l][r+1][t][2],tm+(x[r]-x[r-1]));
                            if((tm+(x[r]-x[r-1]))<=tme[r])
                            {
                                dp[l][r+1][t+1][2]=min(dp[l][r+1][t+1][2],tm+(x[r]-x[r-1]));
                            }
                        }
                    }
                }
            }
        }
    }
    // cout<<dp[1][0][1][0]<<' '<<dp[1][0][1][1]<<' '<<dp[1][0][1][2]<<endl;
    // cout<<dp[2][0][2][0]<<' '<<dp[2][0][2][1]<<' '<<dp[2][0][2][2]<<endl;
    // cout<<dp[2][1][3][0]<<' '<<dp[2][1][3][1]<<' '<<dp[2][1][3][2]<<endl; // ? ? 11
    // cout<<dp[2][2][3][0]<<' '<<dp[2][2][3][1]<<' '<<dp[2][2][3][2]<<endl; // 4
    // cout<<dp[2][3][4][0]<<' '<<dp[2][3][4][1]<<' '<<dp[2][3][4][2]<<endl;
    ll ans=0;
    for(int j=n;j>=0;j--)
    {
        for(int l=0;l<=n;l++)
        {
            for(int r=0;r+l<=n;r++)
            {
                for(int t=0;t<3;t++)
                {
                    if(dp[l][r][j][t]<1e18)
                    {
                        cout<<j<<endl;
                        return 0;
                        // ans=j;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
}

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