Submission #1090835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090835		4QT0R	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	66 ms	8140 KiB

bridge

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

priority_queue<ll> lewo;
priority_queue<ll,vector<ll>,greater<ll>> prawo;
ll suml,sump;

void ins(ll v){
	ll med=lewo.size()?lewo.top():((1e9)+3);
	if (v<=med){
		lewo.push(v);
		suml+=v;
	}
	else{
		prawo.push(v);
		sump+=v;
	}
	if (lewo.size()<prawo.size()){
		ll x=prawo.top();
		prawo.pop();
		sump-=x;
		lewo.push(x);
		suml+=x;
	}
	else if (prawo.size()+1<lewo.size()){
		ll x=lewo.top();
		lewo.pop();
		suml-=x;
		prawo.push(x);
		sump+=x;
	}
}

ll dp[100003];

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

	ll k,n;
	cin >> k >> n;
	vector<pair<ll,ll>> vec;
	vec.push_back({0,0});
	ll same=0;
	for (ll i = 1; i<=n; i++){
		char a,b;
		ll x,y;
		cin >> a >> x >> b >> y;
		if (a==b)same+=labs(x-y);
		else{
			vec.push_back({x,y});
		}
	}
	n=vec.size()-1;
	same+=n;
	sort(vec.begin(),vec.end(),[](pair<ll,ll> a, pair<ll,ll> b){return a.first+a.second<b.first+b.second;});
	for (ll i = 1; i<=n; i++){
		ins(vec[i].first);
		ins(vec[i].second);
		dp[i]=sump-suml;
	}
	ll ans=dp[n];
	if (k==2){
		for(;lewo.size();lewo.pop());
		for(;prawo.size();prawo.pop());
		suml=sump=0;
		for (ll i = n; i>0; i--){
			ins(vec[i].first);
			ins(vec[i].second);
			ans=min(ans,dp[i-1]+sump-suml);
		}
	}
	cout << same+ans << '\n';
}

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