Submission #1001347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001347		hippo123	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	604 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(temp); lft.pop();
		rsum+=temp; lsum-=temp;
	}
	else if(lft.size()<rht.size()){
		int temp=rht.top();
		lft.push(temp); 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{
			nlist.push_back({num1, num2});
		}
	}
	dist1+=(int)nlist.size();
	sort(nlist.begin(), nlist.end(), comp);
	

	ll lsum, rsum;	
	lsum=0; rsum=0;
	vector<int> pfix(100100, 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;
	}
	ll ans=pfix[(int)nlist.size()-1];
	
	if(nb==2){
	// for nd=2 case
		while(!lft.empty()) lft.pop();
		while(!rht.empty()) rht.pop();
		lsum=0; rsum=0;
		for (int i=(int)nlist.size()-1; 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+dist1; return 0;	
}

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