Submission #1000612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000612		hippo123	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	2 ms	4188 KiB

bridge

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

#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second

	priority_queue<int> lft;
	priority_queue<int, vector<int>, greater<int>> rht;


bool comp(pr a, pr b){
	return a.f+a.s<b.f+b.s;
}

void dataInsert(int elem, ll &lsum, ll &rsum){
	
	int mid=(int)lft.size()?lft.top(): 1e9;

	if(elem>mid) {rht.push(elem); rsum+=elem;}
	else {lft.push(elem); lsum+=elem;}

	// move between lft & rht;
	if(rht.size()+1<lft.size()){ //r to l
		int temp=lft.top();
		rht.push(lft.top()); lft.pop();
		rsum+=temp; lsum-=temp;
	}
	else if(lft.size()<rht.size()){
		int temp=rht.top();
		lft.push(rht.top()); rht.pop();
		lsum+=temp; rsum-=temp;	
	}	
}


int main(){
	int nb, n; cin>>nb>>n;
	vector<pr> nlist;

	ll dist1=0; 
	for (int i=0; i<n; i++){
		char s1, num1, s2, num2;
		cin>>s1>>num1>>s2>>num2;
		if(s1==s2) dist1+=abs(num1-num2);
		else{
			if(num1>num2) swap(num1, num2);
			nlist.push_back({num1, num2});
		}
	}
	sort(nlist.begin(), nlist.end(), comp);
	
	priority_queue<int> lft;
	priority_queue<int, vector<int>, greater<int>> rht;
	ll lsum, rsum;	
	lsum=0; rsum=0;
	vector<int> pfix(1000001, 0);
	for (int i=0; i<(int)nlist.size(); i++){
		dataInsert(nlist[i].f, lsum, rsum);
		dataInsert(nlist[i].s, lsum, rsum);
		pfix[i]=rsum-lsum;
	}
	int n1=(int)nlist.size()-1; 
	if(nb==1) {
		cout<<pfix[n1]+(int)nlist.size()+dist1; return 0;
	}
	ll ans=pfix[n1];
	// for nd=2 case
	while(!lft.empty()) lft.pop();
	while(!rht.empty()) rht.pop();
	lsum=0; rsum=0;
	for (int i=n1; i>=0; i--){
		dataInsert(nlist[i].f, lsum, rsum);
		dataInsert(nlist[i].s, lsum, rsum);
		ans=min(ans, pfix[i-1]+rsum-lsum);
	}

	cout<<ans+(int)nlist.size()+dist1; return 0;
	
	
}

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