Submission #230144

#	Time	Username	Problem	Language	Result	Execution time	Memory
230144		Andrei_Cotor	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	92 ms	67004 KiB

ho_t3

#include<iostream>
#include<algorithm>

using namespace std;

int Poz[205],T[205];
long long Dp[2][205][205][205];

void propag(int tip, int i, int j, int nr, long long time)
{
    if(tip==0)
    {
        if(T[i]>=time)
            nr++;
    }
    else if(T[j]>=time)
    {
        nr++;
    }

    Dp[tip][i][j][nr]=min(Dp[tip][i][j][nr],time);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,l;
    cin>>n>>l;
    
    for(int i=1; i<=n; i++)
        cin>>Poz[i];
    Poz[n+1]=l;

    for(int i=1; i<=n; i++)
        cin>>T[i];

    for(int i=0; i<2; i++)
    {
        for(int j=0; j<=n; j++)
        {
            for(int k=j+1; k<=n+1; k++)
            {
                for(int l=0; l<=j+n-k+1; l++)
                {
                    Dp[i][j][k][l]=1e18;
                }
            }
        }
    }

    Dp[0][0][n+1][0]=Dp[1][0][n+1][0]=0;
    for(int i=0; i<n; i++)
    {
        for(int j=n+1; j>=i+2; j--)
        {
            for(int k=0; k<=i+n-j+1; k++)
            {
                if(Dp[0][i][j][k]==1e18 && Dp[1][i][j][k]==1e18)
                    continue;

                propag(0,i+1,j,k,Dp[0][i][j][k]+Poz[i+1]-Poz[i]);
                propag(1,i,j-1,k,Dp[0][i][j][k]+Poz[i]+l-Poz[j-1]);
                propag(1,i,j-1,k,Dp[1][i][j][k]+Poz[j]-Poz[j-1]);
                propag(0,i+1,j,k,Dp[1][i][j][k]+l-Poz[j]+Poz[i+1]);
            }
        }
    }

    int rez=0;
    for(int i=0; i<=n; i++)
    {
        for(int j=rez+1; j<=n; j++)
        {
            if(Dp[0][i][i+1][j]!=1e18 || Dp[1][i][i+1][j]!=1e18)
                rez=j;
        }
    }
    cout<<rez<<"\n";
    return 0;
}

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