#include "closing.h" #include <bits/stdc++.h> using namespace std; long long pos[200003]; long long cost1[200003]; long long cost2[200003]; long long pfx1[200003]; long long check[200003]; int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { int n=N; int x=X; int y=Y; long long k=K; for(int i=0;i<=200001;i++){ check[i]=0; } for(int i=0;i<n-1;i++){ pos[i+1]=pos[i]+W[i]; } for(int i=0;i<n;i++){ cost1[i]=min(abs(pos[i]-pos[x]),abs(pos[i]-pos[y])); cost2[i]=max(abs(pos[i]-pos[x]),abs(pos[i]-pos[y]))-cost1[i]; pfx1[i+1]=pfx1[i]+cost1[i]; } priority_queue <pair <long long,int> > pq; long long mcost=k; long long ans=0,tans=0; int tpos; //phase 1: chi nang cap cac diem len toi da lv1 for(int i=0;i<n;i++){ pq.push({-cost1[i],i}); } ans=0; while(mcost>0&&!pq.empty()){ mcost+=pq.top().first; ans++; pq.pop(); } if(mcost<0){ ans--; } tans=max(tans,ans); while(!pq.empty()){ pq.pop(); } //phase 2: co ca loai 1 lan 2. Khi do, thang loai 2 chi duoc accept khi o day da co 1 roi mcost=k; mcost-=(pfx1[y+1]-pfx1[x]); if(mcost>0){ ans=0; for(int i=0;i<n;i++){ if(i<x||i>y){ pq.push({-cost1[i],i}); }else{ pq.push({0,i}); } } while(!pq.empty()&&mcost>0){ mcost+=pq.top().first; if(mcost>=0){ ans++; tpos=pq.top().second; pq.pop(); check[tpos]++; if(check[tpos]==1){ pq.push({-cost2[tpos],tpos}); } } } tans=max(tans,ans); } while(!pq.empty()){ pq.pop(); } return tans; }