Submission #932478

#	Time	Username	Problem	Language	Result	Execution time	Memory
932478		VMaksimoski008	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	118 ms	5572 KiB

bridge

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

priority_queue<int> L;
priority_queue<int, vector<int>, greater<int> > R;
ll sumL = 0, sumR = 0;

void insert(int x) {
    int med = (L.empty() ? 1e9 + 1 : L.top());
    if(x <= med) L.push(x), sumL += x;
    else R.push(x), sumR += x;

    if(L.size() > R.size() + 1) {
        R.push(L.top());
        sumL -= L.top();
        sumR += L.top();
        L.pop();
    } else if(R.size() > L.size()) {
        L.push(R.top());
        sumL += R.top();
        sumR -= R.top();
        R.pop();
    }
}

int32_t main() {
    int k, n;
    cin >> k >> n;

    ll ans = 0, ans2 = 0;
    vector<pii> v;
    v.push_back({ 0, 0 });

    for(int i=0; i<n; i++) {
        char a, b;
        int c, d;
        cin >> a >> c >> b >> d;

        if(a == b) {
            ans2 += abs(c - d);
        } else {
            v.push_back({ c, d });
            ans2++;
        }
    }

    if(v.size() == 1) {
        cout << ans2 << '\n';
        return 0;
    }

    if(k == 1) {
        for(int i=1; i<v.size(); i++) {
            insert(v[i].first);
            insert(v[i].second);
        }

        ans = sumR - sumL;
    } else {
        ans = 1e18;

        sort(1+all(v), [&](pii &a, pii &b) { return (a.first + a.second) < (b.first + b.second); });

        vector<ll> pref(v.size());
        for(int i=1; i<v.size(); i++) {
            insert(v[i].first);
            insert(v[i].second);
            pref[i] = sumR - sumL;
        }

        sumL = sumR = 0;
        while(!L.empty()) L.pop();
        while(!R.empty()) R.pop();

        for(int i=v.size()-1; i>0; i--) {
            insert(v[i].first);
            insert(v[i].second);
            ans = min(ans, pref[i-1] + sumR - sumL);
        }
    }

    cout << ans + ans2 << '\n';
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=1; i<v.size(); i++) {
      |                      ~^~~~~~~~~
bridge.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=1; i<v.size(); i++) {
      |                      ~^~~~~~~~~

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