Submission #469877

#	Time	Username	Problem	Language	Result	Execution time	Memory
469877		amirmohammad_nezami	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	102 ms	7228 KiB

bridge

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

#define F first
#define S second
#define ll long long
#define PB push_back
#define int long long
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse4,avx,avx2")

const ll maxn = 1e5 + 4 , N = 2e6 + 4 , mod = 1e9 + 7 , INF = 1e18 + 4 , lg = 43;

int n , k , sumL , sumR , sumT , pre[maxn] , suf[maxn];
priority_queue <int> L , R;
vector <pii> vec;

inline bool cmp(pii a , pii b) {
    return a.F + a.S < b.F + b.S;
}

void add(int x) {
    int med = (_sz(L) ? L.top() : INF);

    if(x <= med) L.push(x) , sumL += x;
    else R.push(-x) , sumR += x;

    if(_sz(L) < _sz(R) - 1) {
        int cur = R.top();
        R.pop(); L.push(-cur);
        sumL += -cur , sumR -= -cur; 
    }
    else if (_sz(L) - 1 > _sz(R)) {
        int cur = L.top();
        L.pop(); R.push(-cur);
        sumR += cur , sumL -= cur;
    }
}

int32_t main() {
    FAST;
    cin >> k >> n;
    for (int i = 0; i < n; ++i) {
        char a , b; int s , t;
        cin >> a >> s >> b >> t;
        if(a == b) sumT += abs(s - t);
        else vec.PB({s , t});
    }
    sort(_all(vec) , cmp);

    for (int i = 0; i < _sz(vec); ++i) {
        add(vec[i].F) , add(vec[i].S);
        int med = L.top();
        pre[i + 1] = (_sz(L) * med - sumL) + (sumR - _sz(R) * med);
    }
    while(_sz(L)) L.pop();
    while(_sz(R)) R.pop();
    sumL = sumR = 0;
    for (int i = _sz(vec) - 1; i >= 0; --i) {
        add(vec[i].F) , add(vec[i].S);
        int med = L.top();
        suf[_sz(vec) - i] = (_sz(L) * med - sumL) + (sumR - _sz(R) * med);
    }

    if(k == 1) {
        cout << pre[_sz(vec)] + sumT + _sz(vec) << '\n';
    }
    else {
        int ans = INF;
        for (int i = 0; i <= _sz(vec); ++i) {
            ans = min(ans , pre[i] + suf[_sz(vec) - i]);
        }
        cout << ans + sumT + _sz(vec) << '\n';
    }
}

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