Submission #425402

#	Time	Username	Problem	Language	Result	Execution time	Memory
425402		penguinhacker	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	79 ms	5828 KiB

bridge

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, k;
ll add, ans, tot, p[mxN];
vector<ar<int, 2>> v;
priority_queue<int> lo;
priority_queue<int, vector<int>, greater<int>> hi;

void ins(int x) {
	if (lo.empty()||x<=lo.top())
		lo.push(x), tot-=x;
	else
		hi.push(x), tot+=x;
	if (lo.size()>hi.size()+1) {
		int x=lo.top(); lo.pop();
		tot+=2*x, hi.push(x);
	}
	if (hi.size()>lo.size()) {
		int x=hi.top(); hi.pop();
		tot-=2*x, lo.push(x);
	}
}

ll get() {
	return tot+(lo.size()-hi.size())*lo.top();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n;
	for (int i=0; i<n; ++i) {
		char a, b;
		int x, y;
		cin >> a >> x >> b >> y;
		if (a==b)
			add+=abs(x-y);
		else {
			++add;
			v.push_back({x, y});
		}
	}
	if (v.empty()) {
		cout << add;
		return 0;
	}
	sort(v.begin(), v.end(), [](ar<int, 2> a, ar<int, 2> b) {return a[0]+a[1]<b[0]+b[1];});
	for (int i=0; i<v.size(); ++i) {
		ins(v[i][0]), ins(v[i][1]);
		p[i]=get();
	}
	ans=p[v.size()-1];
	if (k==2) {
		tot=0;
		priority_queue<int>().swap(lo);
		priority_queue<int, vector<int>, greater<int>>().swap(hi);
		for (int i=v.size()-1; i; --i) {
			ins(v[i][0]), ins(v[i][1]);
			ans=min(ans, p[i-1]+get());
		}
	}
	cout << add+ans;
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i=0; i<v.size(); ++i) {
      |                ~^~~~~~~~~

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