Submission #1179268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179268		alexander707070	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	59 ms	4804 KiB

bridge

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const int inf=1e9+7;
const long long inff=1e17;

struct house{
	int x,y;

	inline friend bool operator < (house fr,house sc){
		return fr.x+fr.y < sc.x+sc.y;
	}
};

struct median{
	priority_queue<int> l;
	priority_queue<int,vector<int>, greater<int> > r;

	long long sumL,sumR;

	void init(){
		l.push(-1);
		r.push(inf);
	}

	void balance(){
		if(r.size()>=l.size()){
			sumR-=r.top();
			sumL+=r.top();

			l.push(r.top()); r.pop();
		}

		if(l.size()>r.size()+1){
			sumL-=l.top();
			sumR+=l.top();

			r.push(l.top()); l.pop();
		}
	}

	void add(int x){
		if(x<=l.top()){
			sumL+=x;
			l.push(x);
		}else{
			r.push(x);
			sumR+=x;
		}

		balance();
	}

	long long calc(){
		long long lt=int(l.size())-1,rt=int(r.size())-1;

		return (long long) lt*l.top()-sumL + sumR-rt*l.top();
	}

}pref,suff;

int n,k,x,y,m,p,q;
long long ans,toadd;
long long costpref[MAXN],costsuff[MAXN];

char s,t;
house h[MAXN];

void solve_easy(){
	pref.init();

	for(int i=1;i<=m;i++){
		pref.add(h[i].x);
		pref.add(h[i].y);
	}
	
	ans+=pref.calc()+m;
	cout<<ans<<"\n";
}

void solve_hard(){
	if(m==0){
		cout<<ans<<"\n";
		return;
	}

	pref.init();
	suff.init();

	for(int i=1;i<=m;i++){
		pref.add(h[i].x);
		pref.add(h[i].y);

		costpref[i]=pref.calc();
	}

	for(int i=m;i>=1;i--){
		suff.add(h[i].x);
		suff.add(h[i].y);

		costsuff[i]=suff.calc();
	}

	long long best=inff;
	for(int i=0;i<=m;i++){
		best=min(best,costpref[i]+costsuff[i+1]);
	}

	ans+=best+m;
	cout<<ans<<"\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>x>>t>>y;
		
		if(s==t){
			ans+=abs(x-y);
			continue;
		}

		m++; h[m]={x,y};
	}

	sort(h+1,h+m+1);

	if(k==1){
		solve_easy();
	}else{
		solve_hard();
	}

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37