Submission #1224795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224795		boclobanchat	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	57 ms	67164 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const int MAXN=205;
const long long INF=1e18;
long long dp[MAXN][MAXN][MAXN][2],A[MAXN],val[MAXN];
void minimize(long long& a,long long b)
{
	if(a>b) a=b;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k,ans=0;
	cin>>n>>k;
	A[n+1]=k;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=0;i<=n+1;i++) for(int j=i;j<=n+1;j++) for(int k=0;k<=n+1;k++) dp[i][j][k][0]=dp[i][j][k][1]=INF;
	dp[0][n+1][0][0]=0;
	for(int i=n;i;i--) for(int l=0;l+i<=n+1;l++)
	{
		int r=l+i;
		for(int p=0;p<=n;p++)
		{
			if(l) 
			{
				minimize(dp[l][r][p+(dp[l-1][r][p][0]+A[l]-A[l-1]<=val[l])][0],dp[l-1][r][p][0]+A[l]-A[l-1]);
				minimize(dp[l][r][p+(dp[l-1][r][p][1]+A[l]+k-A[r]<=val[l])][0],dp[l-1][r][p][1]+A[l]+k-A[r]);
			}
			if(r<=n)
			{
				minimize(dp[l][r][p+(dp[l][r+1][p][0]+A[l]+k-A[r]<=val[r])][1],dp[l][r+1][p][0]+A[l]+k-A[r]);
				minimize(dp[l][r][p+(dp[l][r+1][p][1]+A[r+1]-A[r]<=val[r])][1],dp[l][r+1][p][1]+A[r+1]-A[r]);
			}
		}
		for(int p=0;p<=n;p++) if(min(dp[l][r][p][0],dp[l][r][p][1])<INF) ans=max(ans,p);
	}
	cout<<ans;
}

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