Submission #993355

#	Time	Username	Problem	Language	Result	Execution time	Memory
993355		BF001	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	69 ms	7912 KiB

bridge

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

#define N 100005
#define int long long
#define fi first
#define se second

typedef pair<int, int> ii;

int same, res, n, lsum, rsum, pre[N];
vector<ii> vec;
priority_queue<int> lq;
priority_queue<int, vector<int>, greater<int>> rq;

void add(int x){
	//cout << x << "\n";
	int tp = 1e18;
	if (lq.size()) tp = lq.top();
	if (x <= tp){
		lq.push(x);
		lsum += x;
	}
	else {
		rq.push(x);
		rsum += x;
	}
	if (rq.size() + 1 < lq.size()){
		tp = lq.top();
		lq.pop();
		rq.push(tp);
		rsum += tp;
		lsum -= tp;
	}
	if (lq.size() < rq.size()){
		tp = rq.top();
		rq.pop();
		lq.push(tp);
		rsum -= tp;
		lsum += tp;
	}
}

bool cmp(ii& a, ii& b){
	return a.fi + a.se < b.fi + b.se;
}

int k;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     
    cin >> k >> n;
    for (int i = 1; i <= n; i++){
    	char aa, bb;
    	int pos1, pos2;
    	cin >> aa >> pos1 >> bb >> pos2;
    	if (aa == bb){
    		same += abs(pos2 - pos1);
    	}
    	else{
    		vec.push_back({pos1, pos2});
    	}
    }  

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

    same += vec.size();

    for (int i = 1; i <= (int) vec.size(); i++){
    	add(vec[i - 1].fi);
    	add(vec[i - 1].se);
    	//cout << rsum << " " << lsum << "\n";
    	pre[i] = rsum - lsum;
    }

    res = pre[vec.size()];
    if (k == 2){
	    lsum = rsum = 0;
	    while (lq.size()) lq.pop();
	    while (rq.size()) rq.pop();
	    for (int i = (int) vec.size(); i >= 1; i--){
	    	add(vec[i - 1].fi);
	    	add(vec[i - 1].se);
	    	res = min(res, pre[i - 1] + rsum - lsum);
	    }
	}
    cout << res + same;

    return 0;
}     

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