제출 #772828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772828		MahmoudMamdouh13	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	340 KiB

bridge

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

#define AzizIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(v) ((v).begin()), ((v).end())
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(v) ((int)(v).size())
#define endl '\n'

#define ull unsigned long long
#define ll long long
#define ld long double
#define MAX (((int)2e6) + 5)
#define mod (((int)1e9) + 7)

bool cmp(pair<int, int> x, pair<int, int> y) {
    return (x.fi + x.se < y.fi + y.se);
}

priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<>> rpq;
ll lsum, rsum;
void insert(int x) {
    int med = sz(lpq)? lpq.top(): 1000000001;
    if (x <= med) {
        lpq.push(x);
        lsum += x;
    } else {
        rpq.push(x);
        rsum += x;
    }

    if (sz(lpq) > sz(rpq) + 1) {
        int nxt = lpq.top();
        lpq.pop();
        lsum -= nxt;
        rpq.push(nxt);
        rsum += nxt;
    } else if (sz(lpq) < sz(rpq)) {
        int nxt = rpq.top();
        rpq.pop();
        rsum -= nxt;
        lpq.push(nxt);
        lsum += nxt;
    }
}
void solve() {
    int k, n;
    cin >> k >> n;
    vector< int > pref(n + 1);
    vector< pair<int, int> > v = {{0, 0}};
    ll same_side = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        int x, y;
        char a, b;
        cin >> a >> x >> b >> y;
        if (a == b) same_side += abs(x - y);
        else v.push_back({x, y});
    }
    sort(v.begin(), v.end(), cmp);
    n = sz(v) - 1;
    same_side += n;
    for (int i = 1; i <= n; ++i) {
        insert(v[i].fi);
        insert(v[i].se);
        pref[i] = rsum - lsum;
    }
    ans = pref[n];
    if (k == 2) {
        while (sz(lpq)) lpq.pop();
        while (sz(rpq)) rpq.pop();
        rsum = lsum = 0;
        for (int i = n; i; --i) {
            insert(v[i].fi);
            insert(v[i].se);
            ans = min(ans, rsum - lsum + pref[i - 1]);
        }
    }
    cout << ans + same_side << endl;
}


int main() {
    AzizIO
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

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