Submission #970974

#	Time	Username	Problem	Language	Result	Execution time	Memory
970974		njoop	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	104 ms	12904 KiB

bridge

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

int n, k, in1, in2, mxl, mnr;
char c1, c2;
vector<pair<int, int>> v;
multiset<int> s1, s2;
ll pref[200010], suff[200010], su1, su2, res, ans;

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.first+a.second < b.first+b.second;
}

void insertVal(int in) {
    if(s1.size() <= s2.size()) {
        s1.insert(in);
        su1 += in;
    } else {
        s2.insert(in);
        su2 += in;
    }
    if(s1.size() && s2.size() && *s1.rbegin() > *s2.begin()) {
        mxl = *s1.rbegin();
        mnr = *s2.begin();
        su1 += mnr - mxl;
        su2 += mxl - mnr;
        s1.insert(mnr);
        s1.erase(s1.find(mxl));
        s2.insert(mxl);
        s2.erase(s2.find(mnr));
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> k >> n;
    for(int i=0; i<n; i++) {
        cin >> c1 >> in1 >> c2 >> in2;
        if(c1 == c2) {
            res += abs(in1 - in2);
            continue;
        }
        v.push_back({in1, in2});
    }
    sort(v.begin(), v.end(), cmp);
    res += v.size();
    for(int i=0; i<v.size(); i++) {
        insertVal(v[i].first);
        insertVal(v[i].second);
        pref[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2;
    }
    ans = pref[v.size()-1];
    if(k == 1) {
        cout << ans+res;
        return 0;
    }
    for(int i=v.size()-1; i>=0; i--) {
        insertVal(v[i].first);
        insertVal(v[i].second);
        suff[i] = (s1.size()-s2.size())*(*s1.rbegin()) - su1 + su2;
    }
    for(int i=0; i<v.size()-2; i++) {
        ans = min(ans, pref[i]+suff[i+1]);
    }
    cout << ans+res;
    return 0;
}

Compilation message (stderr)

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

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