제출 #1281461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281461		Jawad_Akbar_JJ	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	110 ms	5720 KiB

bridge

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define int long long
const int N = 100005, K = 700;
priority_queue<int> pQ, dm1;
priority_queue<int, vector<int>, greater<int>> Pq, dm2;
int Sum1, Sum2, pre[N];

int insert(int l, int r){
	pQ.push(l);
	Pq.push(r);
	Sum2 += r, Sum1 += l;

	while (Pq.top() < pQ.top()){
		int k1 = pQ.top(), k2 = Pq.top();
		pQ.pop(), Pq.pop();
		Sum1 += -k1 + k2, Sum2 += -k2 + k1;
		Pq.push(k1), pQ.push(k2);
	}
	return Sum2 - Sum1;
}

signed main(){
	int k, n, Ans = 0, Ans1 = 1e17;
	cin>>k>>n;

	vector<pair<int,int>> vec;
	for (int i=1;i<=n;i++){
		char a, c;
		int b, d;
		cin>>a>>b>>c>>d;
		if (b >= d)
			swap(b, d);

		if (a == c)
			Ans += d - b;
		else{
			vec.push_back({b + d, b});
			Ans++;
		}
	}

	sort(begin(vec), end(vec));

	n = vec.size();

	for (int i=0;i<n;i++)
		pre[i] = insert(vec[i].second, vec[i].first - vec[i].second);
	
	if (k == 1 or n == 0)
		return cout<<(n == 0 ? 0 : pre[n-1]) + Ans<<'\n', 0;

	pQ = dm1;
	Pq = dm2;
	Sum1 = Sum2 = 0;

	for (int i=n-1;i>=0;i--)
		Ans1 = min(Ans1, Ans + insert(vec[i].second, vec[i].first - vec[i].second) + (i == 0 ? 0 : pre[i-1]));
	cout<<Ans1<<endl;
}

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