Submission #682525

#	Time	Username	Problem	Language	Result	Execution time	Memory
682525		79brue	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	54 ms	4032 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll base, ans;
ll a[100002], b[100002];

void push(priority_queue<ll> &pq1, priority_queue<ll, vector<ll>, greater<ll> > &pq2, ll &sum1, ll &sum2, ll x){
    pq1.push(x); sum1 += x;
    if(pq1.size() > pq2.size() + 1){
        pq2.push(pq1.top()), sum2 += pq1.top();
        sum1 -= pq1.top(); pq1.pop();
    }
}

ll getAns(priority_queue<ll> &pq1, priority_queue<ll, vector<ll>, greater<ll> > &pq2, ll &sum1, ll &sum2){
    return (sum2 - pq1.top() * (ll)pq2.size()) + (pq1.top() * (ll)pq1.size() - sum1);
}

void solve2(){
    vector<pair<ll, ll> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(a[i], b[i]));
    sort(vec.begin(), vec.end(), [&](auto x, auto y){
        return (x.first + x.second) < (y.first + y.second);
    });

    ans = 1e18;

    priority_queue<ll> pq1;
    priority_queue<ll, vector<ll>, greater<ll> > pq2;
    ll sum1 = 0, sum2 = 0;

    vector<ll> sumL (n+1);
    vector<ll> sumR (n+1);

    for(int i=0; i<n; i++){
        push(pq1, pq2, sum1, sum2, vec[i].first);
        push(pq1, pq2, sum1, sum2, vec[i].second);
        sumL[i+1] = getAns(pq1, pq2, sum1, sum2);
    }

    while(!pq1.empty()) pq1.pop();
    while(!pq2.empty()) pq2.pop();
    sum1 = sum2 = 0;
    for(int i=n-1; i>=0; i--){
        push(pq1, pq2, sum1, sum2, vec[i].first);
        push(pq1, pq2, sum1, sum2, vec[i].second);
        sumR[i] = getAns(pq1, pq2, sum1, sum2);
    }

    for(int i=0; i<=n; i++) ans = min(ans, sumL[i] + sumR[i]);

    printf("%lld", ans+base+n);
}

int main(){
    scanf("%d %d", &k, &n);
    for(int i=1; i<=n; i++){
        char C1, C2;
        int X1, X2;
        scanf(" %c %d %c %d", &C1, &X1, &C2, &X2);
        if(C1==C2) base += abs(X1-X2), n--, i--;
        else a[i] = X1, b[i] = X2;
    }
    if(n==0){
        printf("%lld", base);
        return 0;
    }
    if(k==1){
        vector<ll> vec;
        for(int i=1; i<=n; i++) vec.push_back(a[i]), vec.push_back(b[i]);
        sort(vec.begin(), vec.end());
        ans = 1e18;

        ll lsum = 0, lcnt = 0, rsum = accumulate(vec.begin(), vec.end(), 0LL), rcnt = (int)vec.size();
        for(int i=0; i<n*2; i++){
            rsum -= vec[i], rcnt--;
            ans = min(ans, (lcnt * vec[i] - lsum) + (rsum - rcnt * vec[i]) + n);
            lsum += vec[i], lcnt++;
        }
        printf("%lld", ans+base);
        return 0;
    }

    solve2();
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d %d", &k, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %c %d %c %d", &C1, &X1, &C2, &X2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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