Submission #1167273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167273		Gurban	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	0 ms	324 KiB

bridge

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

using ll = long long;

const int maxn=1e5+5;
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();
			m1.insert(*m2.begin());
			m2.insert(*m1.rbegin());
			m1.erase(*m1.rbegin());
			m2.erase(*m2.begin());
		}
		// cout<<i<<" ---> \n";
		// for(auto j : m1) cout<<j<<' ';
		// cout<<'\n';
		// for(auto j : m2) cout<<j<<' ';
		// cout<<"\n"<<sm<<' '<<bg<<'\n';
		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(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<<i<<' '<<lft[i]<<' '<<rgt[n-i-2]<<'\n';
	}
	cout<<ans + jog + n;
}

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