Submission #1276684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276684		PieArmy	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	44 ms	33392 KiB

ho_t3

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n,k;
int loc[223],t[223];
int dp[202][202][202][2];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>loc[i];
	}
	for(int i=1;i<=n;i++){
		cin>>t[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=i+1;j<=n+1;j++){
			for(int l=0;l<=n;l++){
				for(int r=0;r<2;r++){
					dp[i][j][l][r]=1e9+1;
				}
			}
		}
	}
	dp[0][n+1][0][0]=0;
	int ans=0;
	for(int res=0;res<=n;res++){
		for(int l=0;l<=n;l++){
			for(int r=n+1;r>l;r--){
				for(int a=0;a<2;a++){
					if(dp[l][r][res][a]==1e9+1)continue;
					if(r-l==1){
						ans=max(ans,res);
						continue;
					}
					if(a==0){
						int res2=res;
						if(t[l+1]>=dp[l][r][res][a]+loc[l+1]-loc[l]){
							res2++;
						}
						dp[l+1][r][res2][a]=min(dp[l][r][res][a]+loc[l+1]-loc[l],dp[l+1][r][res2][a]);
						res2=res;
						if(t[r-1]>=dp[l][r][res][a]+loc[l]+k-loc[r-1]){
							res2++;
						}
						dp[l][r-1][res2][1]=min(dp[l][r][res][a]+loc[l]+k-loc[r-1],dp[l][r-1][res2][1]);
					}
					else{
						int res2=res;
						if(t[l+1]>=dp[l][r][res][a]+loc[l+1]+k-loc[r]){
							res2++;
						}
						dp[l+1][r][res2][0]=min(dp[l][r][res][a]+loc[l+1]+k-loc[r],dp[l+1][r][res2][0]);
						res2=res;
						if(t[r-1]>=dp[l][r][res][a]+loc[r]-loc[r-1]){
							res2++;
						}
						dp[l][r-1][res2][a]=min(dp[l][r][res][a]+loc[r]-loc[r-1],dp[l][r-1][res2][a]);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
}

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