Submission #257045

#	Time	Username	Problem	Language	Result	Execution time	Memory
257045		akat	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	112 ms	127736 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const long long N = 201;
long long t[N], x[N], ans;
long long dp[N][N][N][2];
void update(long long l,long long r,long long cnt,long long j,long long time)
{
	long long cur = l;
	if(j) cur = r;
	if(t[cur] >= time) cnt++;
	long long &curr = dp[l][r][cnt][j];
	if(curr == -1 || curr > time) curr = time;
	ans = max(ans, cnt);
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n, la, i, j, k;
	cin>>n>>la;
	for(i = 1; i <= n; i++)
		cin>>x[i];
	for(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, la - x[n]);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= i; j++)
			for(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)
				{
					long long time = dp[l][r][k][0];
					update(l+1, r, k, 0, time + x[l+1] - x[l]);
					update(l+1, r, k, 1, time + x[l] + la - x[r]);
				}
				if(dp[l][r][k][1] != -1)
				{
					long long time = dp[l][r][k][1];
					update(l, r-1, k, 1, time + x[r] - x[r-1]);
					update(l, r-1, k, 0, time + la - x[r] + x[l]);
				}
			}
	cout<<ans<<'\n';
}

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