제출 #332941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332941		Cantfindme	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	175 ms	10332 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
typedef pair<int, pi> pii;
#define all(x) x.begin(),x.end()

const int maxn = 100010;
const int INF = LLONG_MAX/2;

//If K=1, take median of all points X and Y independently
//Take b_left if x + y < b_right + b_left else take b_right
//Just have to find splitting point 
//If unoptimal (take wrong bridge in wrong group) then whatever.

int pref[maxn];
int suf[maxn];
int k, n;
int bonus;

vector <pi> v;
pi pos[maxn];

priority_queue <int> q1;
priority_queue <int,vector<int>,greater<int>> q2;

int q1sum, q2sum;

void movee(int opt) {
	if (opt and !q1.empty()) {
		int x = q1.top();
		q1.pop();
		q2.push(x);
		q1sum -= x;
		q2sum += x;
	} else if (!opt and !q2.empty()) {
		int x = q2.top();
		q2.pop();
		q1.push(x);
		q2sum -= x;
		q1sum += x;
	}
}

int findMed() {
	if (q1.size() == 0 and q2.size() == 0) return 0;
	if (q1.size() >= q2.size()) {
		return q1.top();
	} else {
		return q2.top();
	}
}

void check() {
	if ((int)q1.size() > (int)q2.size() + 1) movee(1);
	else if ((int)q2.size() > (int)q1.size() + 1) movee(0);
}

void insert(int x) {
	int med = findMed();
	if (x > med) {
		q2.push(x);
		q2sum += x;
	} else {
		q1.push(x);
		q1sum += x;
	}
	check();
}

int32_t main() {
	cin >> k >> n;
	for (int i =0;i<n;i++) {
		char a,b; cin >> a >> pos[i].f >> b >> pos[i].s;
		if (a == b) bonus += abs(pos[i].f - pos[i].s);
		else {
			v.push_back(pi(pos[i].f+pos[i].s,i));
		}
	}
	
	sort(all(v));
	for (int i =0;i<(int)v.size();i++) {
		int x = pos[v[i].s].f, y = pos[v[i].s].s;
		insert(x);
		insert(y);
		int med = findMed();
		pref[i] = (q2sum - med * q2.size()) + (med * q1.size() - q1sum);
	}

	if (k == 1) {
		cout << pref[v.size()-1] + bonus + (int)v.size();
		return 0;
	}
	
	while (!q1.empty()) q1.pop();
	while (!q2.empty()) q2.pop();
	q1sum = q2sum = 0;
	for (int i =(int)v.size()-1;i>=0;i--) {
		int x = pos[v[i].s].f, y = pos[v[i].s].s;
		insert(x);
		insert(y);
		int med = findMed();
		suf[i] = (q2sum - med * q2.size()) + (med * q1.size() - q1sum);
	}

	int ans = suf[0] + bonus + (int) v.size();
	for (int i =0;i<(int)v.size();i++) {
		ans = min(ans, pref[i] + suf[i+1] + bonus + (int)v.size());
	}
	
	cout << ans;
}

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