Submission #980024

#	Time	Username	Problem	Language	Result	Execution time	Memory
980024		vjudge1	Closing Time (IOI23_closing)	C++17	0 / 100	45 ms	10324 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;

const int lim=2e5+5;
vector<pii> adj[lim];
ll ant[lim], nxt[lim];
bool vis[lim];
ll K2, a[lim];

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
	if(K>3000) return 0;
	rep(i,0,N) adj[i].clear(), a[i]=0;
	rep(i,0,N-1){
		if(U[i]<V[i]) nxt[U[i]]=W[i], ant[V[i]]=W[i];
		else ant[U[i]]=W[i], nxt[V[i]]=W[i];
	}
	int ans=0, ANS=0;
	K2=K;
	rep(i,0,N+1){
		rep(j,0,N+1){
			ans=0;
			int l=X, r=Y, act;
			K=K2;
			ll sum=0, sumx=0, sumy=0, dis[N]{}, disx[N]{}, disy[N]{};
			priority_queue<ll, vector<ll>, greater<ll>> pq;
			sum=0;
			act=X;
			rep(k,X,N) disx[k]=sum, sum+=nxt[k];
			sum=0;
			repr(k,X+1,0) disx[k]=sum, sum+=ant[k];
			sum=0;
			rep(k,Y,N) disy[k]=sum, sum+=nxt[k];
			sum=0;
			repr(k,Y+1,0) disy[k]=sum, sum+=ant[k];
			sum=0;
			rep(k,0,i+1){
				dis[act]=sum;
				K-=sum;
				sum+=ant[act];
				if(sum>K || act==0) break;
				act--;
			}
			sum=0;
			act=Y;
			rep(k,0,j+1){
				dis[act]=sum;
				K-=sum;
				sum+=nxt[act];
				if(sum>K || act==N-1) break;
				act++;
			}
			sumx=0;
			sumy=0;
			while(l<r){
				if(min(sumx+nxt[l],sumy+ant[r])>K) break;
				if(sumx+nxt[l]<sumy+nxt[r]){
					sumx+=nxt[l];
					K-=sumx;
					l++;
					dis[l]=sumx;
				}else{
					sumy+=ant[r];
					K-=sumy;
					r--;
					dis[r]=sumy;
				}
			}
			rep(i,0,N){
				pq.push(max(0ll,disx[i]-dis[i]));
				pq.push(max(0ll,disy[i]-dis[i]));
			}
			while(pq.size()){
				if(K<pq.top()) break;
				ans++;
				K-=pq.top();
				pq.pop();
			}
			ANS=max(ans,ANS);
		}
	}
	return ANS;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17