Submission #536343

#	Time	Username	Problem	Language	Result	Execution time	Memory
536343		fcw	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	142 ms	5468 KiB

bridge

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

using pii = pair<int, int>;
bool cmp(pii a, pii b){
	return a.st + a.nd < b.st + b.nd;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int k, n;
	cin>>k>>n;
	vector<pii>v = {{0, 0}};
	lint bonus = 0;
	for(int i=0;i<n;i++){
		char a,b;
		int c,d;
		cin>>a>>c>>b>>d;
		if(c > d) swap(c, d);
		if(a == b) bonus += d - c;
		else{
			bonus++;
			v.push_back({c, d});
		}
	}
	sort(v.begin(), v.end(), cmp);
	n = (int)v.size();
	priority_queue<int>lpq;
	priority_queue<int, vector<int>, greater<int>>rpq;

	lint lsum = 0, rsum = 0;
	auto ins = [&](int x)->void{
		int median = (lpq.empty() ? inf : lpq.top());
		if(x <= median){
			lpq.push(x);
			lsum += x;
		}
		else{
			rpq.push(x);
			rsum += x;
		}
		if(rpq.size() < 1 + lpq.size()){
			int top = lpq.top();
			lpq.pop();
			rpq.push(top);
			lsum -= top;
			rsum += top;
		}
		if(lpq.size() < rpq.size()){
			int top = rpq.top();
			rpq.pop();
			lpq.push(top);
			lsum += top;
			rsum -= top;
		}
	};
	vector<lint>pref(n);
	for(int i=1;i<n;i++){
		ins(v[i].st);
		ins(v[i].nd);
		pref[i] = rsum - lsum;
	}
	lint ans = pref[n-1];
	if(k == 2){
		lsum = rsum = 0;
		while(!lpq.empty()) lpq.pop();
		while(!rpq.empty()) rpq.pop();
		for(int i=n-1;i;i--){
			ins(v[i].st);
			ins(v[i].nd);
			ans = min(ans, rsum - lsum + pref[i-1]);
		}
	}
	ans += bonus;
	cout<<ans<<"\n";
	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

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