Submission #203432

#	Time	Username	Problem	Language	Result	Execution time	Memory
203432		mraron	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	831 ms	127612 KiB

ho_t3

#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;
}

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