제출 #1325605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325605		JuanJL	Collecting Stamps 3 (JOI20_ho_t3)	C++20	큐에 대기중	0 ms	0 KiB

ho_t3

#include <bits/stdc++.h>

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

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

#define INF ((ll)1000000000)

const int MAXN = 201;

struct Node{
	ll left;
	ll right;
	ll type; // 0 left 1 right
	ll cnt;
	Node(ll left, ll right,ll type,  ll cnt): left(left), right(right), type(type) , cnt(cnt) {}
};

bool operator<(const Node &a, const Node &b){
	if(a.cnt!=b.cnt) return a.cnt<b.cnt;
	if(a.right-a.left !=b.right-b.left) return a.right-a.left < b.right-b.left;
	return a.type<b.type;
}

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

//IMPORTANTE
//acordarse de tener punto 1 

ll best = 0;
ll dist[MAXN][MAXN][3][MAXN];

void dijkstra(){
	
	mset(dist,-1);

	priority_queue<pair<ll,Node>> pq; pq.push({0,Node(0,SZ(point)-1,0,0)});


	while(!pq.empty()){
		ll cost = pq.top().fst*-1;
		Node rnd = pq.top().snd;
		ll l = rnd.left;
		ll r = rnd.right;
		ll t = rnd.type;
		ll cnt = rnd.cnt;
		pq.pop();
		if(dist[l][r][t][cnt]!=-1) continue;
		/*cout<<l<<" "<<r<<" "<<t<<" "<<cnt<<" "<<cost<<'\n';
		cout<<point[l].fst<<" -- "<<point[r].fst<<'\n';*/
		dist[l][r][t][cnt]=cost;
		best=max(best, cnt);
		if(t==1){
		
			{
				ll nl = l;
				ll nr = r-1;
				ll nt = t;
				if(nl<nr){
					ll ncost = cost + abs(point[r].fst-point[nr].fst);
					ll ncnt = cnt + (ncost<=point[nr].snd?1:0);
					pq.push({ncost*-1, Node( nl, nr, nt, ncnt )});
				}
			}
			
			{
				ll nl = l+1;
				ll nr = r;
				ll nt = (t+1)%2;
				if(nl<nr){
					ll ncost = cost + abs((L-point[r].fst)+point[nl].fst);
					ll ncnt = cnt + (ncost<=point[nl].snd?1:0);
					pq.push({ncost*-1, Node( nl, nr, nt, ncnt )});
				}
			}
			
		}else{
			{
				ll nl = l;
				ll nr = r-1;
				ll nt = (t+1)%2;
				if(nl<nr){
					ll ncost = cost + abs((L-point[nr].fst)+point[l].fst);
					ll ncnt = cnt + (ncost<=point[nr].snd?1:0);
					pq.push({ncost*-1, Node( nl, nr, nt, ncnt )});
				}
			}
						
			{
				ll nl = l+1;
				ll nr = r;
				ll nt = t;
				if(nl<nr){
					ll ncost = cost + abs(point[l].fst-point[nl].fst);
					ll ncnt = cnt + (ncost<=point[nl].snd?1:0);
					pq.push({ncost*-1, Node( nl, nr, nt, ncnt )});
				}
			}
		}
	}
}


int main(){ FIN;
	cin>>n>>L;
	
	point.clear();
	point.resize(n);

	forn(i,0,n) cin>>point[i].fst;
	forn(i,0,n) cin>>point[i].snd;

	sort(ALL(point));

	point.pb({0,-1});
	point.pb({L,-1});

	sort(ALL(point));
		
	dijkstra();


	cout<<best<<'\n';
	return 0;
}