제출 #657906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657906		TS_2392	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	87 ms	5220 KiB

bridge

#include <bits/stdc++.h>
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)

#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound

#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;
const int N = 1e5 + 3, oo = 1e9 + 3;
bool cmp(const pii &a, const pii &b){
    return a.fi + a.se < b.fi + b.se;
}
pii a[N];
int k, n, sz;
ll res, sumup, sumlow, cost[N];
void sol1(){
    int tmp[N << 1], median;
    for(int i = 1; i <= sz; ++i){
        tmp[i] = a[i].fi;
        tmp[i + sz] = a[i].se;
    }
    sort(tmp + 1, tmp + 1 + 2 * sz);
    median = tmp[sz];
    for(int i = 1; i <= 2 * sz; ++i){
        res += (ll)abs(tmp[i] - median);
    }
    cout << res;
}
priority_queue<int> lowq;
priority_queue<int, vector<int>, greater<int> > upq;
void balace(){
    if (upq.size() + 1 < lowq.size()) {
		int nxt = lowq.top();
		lowq.pop();
		upq.push(nxt);
		sumlow -= nxt;
		sumup += nxt;
	} else if (lowq.size() < upq.size()) {
		int nxt = upq.top();
		upq.pop();
		lowq.push(nxt);
		sumup -= nxt;
		sumlow += nxt;
	}
}
void ins(int x){
    int median = (lowq.size() ? lowq.top() : 1000000001);
    if (x <= median) {
		lowq.push(x);
		sumlow += x;
	} else {
		upq.push(x);
		sumup += x;
	}
    balace();
}
void sol2(){
    sort(a + 1, a + 1 + sz, cmp);
    sumup = sumlow = 0;
    for(int i = 1; i <= sz; ++i){
        ins(a[i].fi); ins(a[i].se);
        cost[i] = sumup - sumlow;
    }
    sumup = sumlow = 0; ll ans = cost[sz];
    while(!lowq.empty()) lowq.pop();
    while(!upq.empty()) upq.pop();
    for(int i = sz; i >= 1; --i){
        ins(a[i].fi); ins(a[i].se);
        ans = min(ans, sumup - sumlow + cost[i - 1]);
    }
    cout << res + ans;
}
int main(){
    SPEED;
    cin >> k >> n;
    for(int i = 1; i <= n; ++i){
        char z1, z2; int p1, p2;
        cin >> z1 >> p1 >> z2 >> p2;
        if(z1 == z2){
            res += (ll)abs(p1 - p2);
            continue;
        }
        ++sz; ++res;
        a[sz] = mp(p1, p2);
    }
    if(k == 1) sol1();
    else sol2();
    return 0;
}

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