Submission #959266

#	Time	Username	Problem	Language	Result	Execution time	Memory
959266		maxFedorchuk	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	80 ms	167340 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;

const long long MX = 220;

long long t[MX], x[MX], ans;
long long dp[MX][MX][MX][2];

void update(long long l,long long r,long long k,long long side,long long time)
{
    long long zar=((side==0)?l:r);
    k+=(t[zar]>=time);
    ans=max(ans,k);

    dp[l][r][k][side]=(((dp[l][r][k][side]==-1)|(dp[l][r][k][side]>time))?time:dp[l][r][k][side]);
}

int main()
{
    cin.tie(0);
	ios_base::sync_with_stdio(0);

	long long n, rd;
	cin>>n>>rd;

	for(long long i = 1; i <= n; i++)
		cin>>x[i];
    
	for(long long i = 1; i <= n; i++)
		cin>>t[i];
    
	memset(dp, -1, sizeof(dp));

	update(1, n, 0, 0, x[1]);
	update(1, n, 0, 1, rd - x[n]);

	for(long long i = 1; i <= n; i++)
    {
        for(long long j = 1; j <= i; j++)
        {
            for(long long k = 0; k <= i; k++)
			{
				long long l = j;
				long long r = n - i + j;

				if(l >= r)
                {
                    continue;
                }
                
				if(dp[l][r][k][0] != -1)
				{
					update(l+1, r, k, 0, dp[l][r][k][0] + x[l+1] - x[l]);
					update(l+1, r, k, 1, dp[l][r][k][0] + x[l] + rd - x[r]);
				}
				if(dp[l][r][k][1] != -1)
				{
					update(l, r-1, k, 1, dp[l][r][k][1] + (x[r] - x[r-1]));
					update(l, r-1, k, 0, dp[l][r][k][1] + (rd - x[r] + x[l]));
				}
			}
        }
    }
		
	cout<<ans<<'\n';
}

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