Submission #1167457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167457		Gurban	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	158 ms	13216 KiB

bridge

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

using ll = long long;

int k,n;

bool cmp(pair<int,int>a,pair<int,int>b){
	return a.first + a.second < b.first + b.second;
}

void f(vector<pair<int,int>>v, vector<ll> &jg){
	multiset<int>m1,m2;
	ll sm = 0, bg = 0;
	for(int i = 0;i < (int)v.size();i++){
		m1.insert(v[i].first);
		sm += v[i].first;

		m2.insert(v[i].second);
		bg += v[i].second;
		
		while(*m1.rbegin() > *m2.begin()){
			sm += *m2.begin() - *m1.rbegin();
			bg += *m1.rbegin() - *m2.begin();
			
			m2.insert(*m1.rbegin());
			m1.insert(*m2.begin());
			

			m2.erase(m2.begin());
			m1.erase(--m1.end());
		}
		jg.push_back(bg-sm);
	}

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> k >> n;
	ll jog = 0;
	vector<pair<int,int>>v;
	for(int i = 1;i <= n;i++){
		char p,q;
		int x,y;
		
		cin >> p >> x >> q >> y;
		if(p == q) jog += abs(x-y);
		else {
			v.push_back({x,y});
		}
	}
	sort(v.begin(),v.end(),cmp);

	n = v.size();

	vector<ll>lft,rgt;
	f(v, lft);

	reverse(v.begin(),v.end());
	f(v,rgt);

	if(n == 0) return cout<<jog,0;

	if(k == 1){
		cout<<jog+lft[n-1]+n;
		return 0;
	}

	ll ans = lft[n-1];
	for(int i = 0;i < n-1;i++){
		ans = min(ans,lft[i] + rgt[n-i-2]);
	}
	cout<<ans + jog + n;
}

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