제출 #203432

#제출 시각아이디문제언어결과실행 시간메모리
203432mraronCollecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
831 ms127612 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,L;
ll x[201], t[201];
ll dp[201][201][2][201];
int dist(int i, int j) {
	return min(abs(x[i]-x[j]), L-abs(x[i]-x[j]));
}
//mikor elég legkésőbb kezdeni
ll solve(int l, int r, int side, int cnt) {
	if(cnt==0) return 1LL<<60;
	if(l>r) {
		return -1LL<<60;
	}
	//cerr<<l<<" "<<r<<" "<<side<<" "<<cnt<<"\n";
	if(dp[l][r][side][cnt]!=-1) return dp[l][r][side][cnt];
	int akt;
	if(side==0) akt=l-1;
	else akt=r+1;
	ll ans=-1LL<<60;
	ans=max(ans, solve(l+1,r,0,cnt)-dist(l,akt));
	ans=max(ans, min(t[l],solve(l+1,r,0,cnt-1))-dist(l,akt));
	ans=max(ans, solve(l,r-1,1,cnt)-dist(r,akt));
	ans=max(ans, min(t[r], solve(l,r-1,1,cnt-1))-dist(r,akt));
	return dp[l][r][side][cnt]=ans;
}

int main() {
	cin>>n>>L;
	for(int i=0;i<n;++i) cin>>x[i];
	for(int i=0;i<n;++i) cin>>t[i];
	memset(dp,-1,sizeof dp);
	int ans=0;
	for(int i=0;i<=n;i++) {
		//cerr<<i<<": "<<solve(0,n-1,1,i)<<"\n";
		if(solve(0,n-1,1,i)>=0) ans=i;
	}
	cout<<ans<<"\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...