Submission #959265

#	Time	Username	Problem	Language	Result	Execution time	Memory
959265		maxFedorchuk	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	47 ms	84056 KiB

ho_t3

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

const int MX = 220;

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

void update(int l,int r,int k,int side,int time)
{
    int 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);

	int n, rd;
	cin>>n>>rd;

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

	x[0] = 0;

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

	for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            for(int k = 0; k <= i; k++)
			{
				int l = j;
				int 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: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75