Submission #224028

#	Time	Username	Problem	Language	Result	Execution time	Memory
224028		errorgorn	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	280 ms	135436 KiB

ho_t3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=start-(start>end);x!=end-(start>end);x+=(start<end?1:-1))
#define all(x) x.begin(),x.end()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a, Args... args) { return max(a,MAX(args...)); }
template<typename... Args>
ll MIN(ll a, Args... args) { return min(a,MIN(args...)); }

#define indexed_set tree<ll, null_type, less<ll>,rb_tree_tag,tree_order_statistics_node_update>

const ll INF=1e18;

int n,l;
ll pos[205];
ll t[205];
ll memo[2][205][205][205];

ll dp(int par,int l,int r,int taken){
	if (memo[par][l][r][taken]!=-1) return memo[par][l][r][taken];
	
	ll res=INF;
	//try dont take anything
	if (par==0 && l!=0){
		res=MIN(res,dp(0,l-1,r,taken)+pos[l]-pos[l-1],dp(1,l-1,r,taken)+pos[l]+(pos[n+1]-pos[r]));
	}
	else if (par==1 && r!=n+1){
		res=MIN(res,dp(1,l,r+1,taken)+pos[r+1]-pos[r],dp(0,l,r+1,taken)+(pos[n+1]-pos[r])+pos[l]);
	}
	
	//now try increase taken by 1
	ll tim;
	if (taken){
		if (par==0 && l!=0){
			tim=dp(0,l-1,r,taken-1)+pos[l]-pos[l-1];
			if (tim<=t[l]) res=min(res,tim);
			tim=dp(1,l-1,r,taken-1)+pos[l]+(pos[n+1]-pos[r]);
			if (tim<=t[l]) res=min(res,tim);
		}
		else if (par==1 && r!=n+1){
			tim=dp(1,l,r+1,taken-1)+pos[r+1]-pos[r];
			if (tim<=t[r]) res=min(res,tim);
			tim=dp(0,l,r+1,taken-1)+(pos[n+1]-pos[r])+pos[l];
			if (tim<=t[r]) res=min(res,tim);
		}
	}
	
	//cout<<par<<" "<<l<<" "<<r<<" "<<taken<<" "<<res<<endl;
	return memo[par][l][r][taken]=res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>l;
	pos[0]=0,pos[n+1]=l;
	rep(x,1,n+1) cin>>pos[x];
	rep(x,1,n+1) cin>>t[x];
	
	memset(memo,-1,sizeof(memo));
	
	memo[0][0][n+1][0]=0;
	memo[1][0][n+1][0]=0;
	
	int ans=0;
	rep(x,0,n+1)
		rep(y,0,n+1)
			if (dp(0,x,x+1,y)<INF || dp(1,x,x+1,y)<INF) ans=max(ans,y);
	
	cout<<ans<<endl;
}

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