제출 #1335814

#제출 시각아이디문제언어결과실행 시간메모리
1335814i271828Bikeparking (EGOI24_bikeparking)C++20
28 / 100
310 ms9800 KiB
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=3e5+5;

const ll INF=1LL<<60;

int N;
ll X[MAX],Y[MAX];
ll A[MAX],B[MAX];

ll calc(ll x){
	copy(X,X+N,A),copy(Y,Y+N,B);
	ll ans=0;
	int i=0,j=N-1;
	while (x){
		while (!A[i]) i++;
		while (!B[j]) j--;
		ll c=min(x,min(A[i],B[j]));
		x-=c,A[i]-=c,B[j]-=c;
		if (j>i) ans-=c;
		if (j<i) ans+=c;
	}
	i=0,j=0;
	while (i<N){
		while (i<N&&!A[i]) i++;
		if (i>=N) break;
		while (!B[j]) j++;
		ll c=min(A[i],B[j]);
		A[i]-=c,B[j]-=c;
		if (j>i) ans-=c;
		if (j<i) ans+=c;
	}
	return ans;
}

int main(){
	cin>>N;
	for (int i=0;i<N;i++) cin>>Y[i];
	for (int i=0;i<N;i++) cin>>X[i];
	ll l=0,r=0;
	for (int i=0;i<N;i++) r+=X[i];
	while (r-l>=3){
		ll m0=l+(r-l)/3;
		ll m1=r-(r-l)/3;
		ll v0=calc(m0),v1=calc(m1);
		if (v0>v1) r=m1;
		else l=m0;
	}
	ll ans=-INF;
	for (int x=l;x<=r;x++) ans=max(ans,calc(x));
	cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...