제출 #1325815

#제출 시각아이디문제언어결과실행 시간메모리
1325815JuanJLCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
520 ms202732 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef D
	#define debug(x) cout << x
#else 
	#define debug(x) //nothing
#endif

using namespace std;
typedef long long ll;

const int MAXN = 205;

#define INF ((ll)10000000000000000)

ll dp[MAXN][MAXN][3][MAXN];


ll N,L;
vector<pair<ll,ll>> point;

ll f(ll l , ll r, ll t, ll cnt){
	ll &res = dp[l][r][t][cnt];
	if(res!=-1) return res;
	if(l==0 && r==SZ(point)-1 && cnt==0) return res=0;
	if(l==0 && r==SZ(point)-1) return res=INF;


	res = INF;

	if(t==0){
		{
			if(l-1>=0){

				// estoy en el extramo izq viniendo desde el extremo izq
				ll ncost = abs(point[l-1].fst-point[l].fst);
				res=min(res, f(l-1, r, t, cnt)+ncost);
				if(cnt>0 && f(l-1,r,t,cnt-1)+ncost<=point[l].snd){
					res=min(res , f(l-1,r,t,cnt-1)+ncost );
				}

				//extremo izq viniendo desde el extremo der
				ncost = L-point[r].fst  + point[l].fst;
				res=min(res , f(l-1,r,(t+1)%2,cnt)+ncost);
				if(cnt>0 && f(l-1,r,(t+1)%2,cnt-1)+ncost<=point[l].snd){
					res=min(res, f(l-1,r,(t+1)%2,cnt-1)+ncost);
				}
				
			}
		}
		
	}else{
		{

			if(r+1<SZ(point)){
			
				// estoy en el extramo der viniendo desde el extremo der
				ll ncost = point[r+1].fst-point[r].fst;
				res=min(res, f(l, r+1, t, cnt)+ncost);
				if(cnt>0 && f(l,r+1,t,cnt-1)+ncost<=point[r].snd){
					res=min(res , f(l,r+1,t,cnt-1)+ncost );
				}

				//extremo der viniendo desde el extremo izq
				ncost = L-point[r].fst  + point[l].fst;
				res=min(res , f(l,r+1,(t+1)%2,cnt)+ncost);
				if(cnt>0 && f(l,r+1,(t+1)%2,cnt-1)+ncost<=point[r].snd){
					res=min(res, f(l,r+1,(t+1)%2,cnt-1)+ncost);
				}		
			}
			
		}	
	}
	
	return res;	
}

int main(){

	cin>>N>>L;

	point.clear();
	point.resize(N+2);

	point[0]={0,-1};
	point[N+1]={L,-1};
	forn(i,1,N+1) cin>>point[i].fst;
	forn(i,1,N+1) cin>>point[i].snd;

	mset(dp,-1);

	ll best = 0;
	forn(l,0,N+1){
		forn(r,l+1,N+2){
			forn(t,0,3){
				forn(cnt,0,N+1){
					if(f(l,r,t,cnt)<INF){
						best=max(best,(ll)cnt);
					}
				}
			}
		}
	}

	cout<<best<<'\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...