Submission #1307087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307087		namhh	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	68 ms	6176 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int n,k,pre[N],suml = 0,sumr = 0;
priority_queue<int>pql;
priority_queue<int,vector<int>,greater<int>>pqr;
vector<pii>v;
bool cmp(pii a, pii b){
	return a.fi+a.se < b.fi+b.se;
}
void add(int val){
	int med = 1e9+1;
	if(pql.size()) med = pql.top();
	if(val <= med){
		pql.push(val);
		suml += val;
	}
	else{
		pqr.push(val);
		sumr += val;
	}
	if(pql.size() > pqr.size()+1){
		int x = pql.top();
		pql.pop();
		pqr.push(x);
		suml -= x;
		sumr += x;
	}
	if(pqr.size() > pql.size()){
		int x = pqr.top();
		pqr.pop();
		pql.push(x);
		sumr -= x;
		suml += x;
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> k >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		char p,q;
		int s,t;
		cin >> p >> s >> q >> t;
		if(p == q) ans += abs(t-s);
		else v.push_back({s,t});
	}
	if(v.empty()){
		cout << ans;
		return 0;
	}
	sort(v.begin(),v.end(),cmp);
	ans += v.size();
	if(k == 1){
		for(int i = 0; i < v.size(); i++){
			add(v[i].fi);
			add(v[i].se);
		}
		ans += sumr-suml;
		cout << ans;
	}
	else{
		for(int i = 0; i < v.size(); i++){
			add(v[i].fi);
			add(v[i].se);
			pre[i] = sumr-suml;
		}
		int mn = pre[v.size()-1];
		while(!pql.empty()) pql.pop();
		while(!pqr.empty()) pqr.pop();
		suml = 0;
		sumr = 0;
		for(int i = v.size()-1; i >= 1; i--){
			add(v[i].fi);
			add(v[i].se);
			mn = min(mn,pre[i-1]+sumr-suml);
		}
		cout << ans+mn;
	}
}

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