Submission #405160

#	Time	Username	Problem	Language	Result	Execution time	Memory
405160		SirCovidThe19th	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	208 ms	6356 KiB

bridge

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

#define ll long long
#define pii pair<int, int>

int n, k; 
ll same, cross, lSum = 0, rSum = 0; 

vector<pii> diff; vector<ll> prefix, suffix;

priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;

bool cmp(pii a, pii b){
    return a.first+a.second < b.first+b.second;
}

void update(int x){
    if (l.size() <= r.size()){
        r.push(x); rSum += x;
        l.push(r.top()); lSum += r.top();
        rSum -= r.top(); r.pop();
    }
    else{
        l.push(x); lSum += x;
        r.push(l.top()); rSum += l.top();
        lSum -= l.top(); l.pop();
    }
}

int main(){
    
    cin >> k >> n; 
    for (int i = 0; i < n; i++){
        char a, b; int x, y; cin >> a >> x >> b >> y;
        if (a == b) same += abs(x-y);
        else diff.push_back({x, y});
    }

    if (diff.size() == 0){
        cout<<same; return 0;
    }

    sort(diff.begin(), diff.end(), cmp);
    prefix.resize(diff.size()); suffix.resize(diff.size());

    for (int i = 0; i < diff.size(); i++){
        update(diff[i].first); update(diff[i].second);
        prefix[i] = (rSum-l.top()*r.size()) + (l.top()*l.size()-lSum);
    }

    while (!l.empty()) l.pop();
    while (!r.empty()) r.pop();
    lSum = 0; rSum = 0;

    for (int i = diff.size()-1; i >= 0; i--){
        update(diff[i].first); update(diff[i].second);
        suffix[i] = (rSum-l.top()*r.size()) + (l.top()*l.size()-lSum);
    }

    cross = prefix[diff.size()-1];
    if (k == 2)
        for (int i = 0; i < diff.size()-1; i++) 
            cross = min(cross, prefix[i]+suffix[i+1]);
    
    cout<<same+cross+diff.size();
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:48: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]
   48 |     for (int i = 0; i < diff.size(); i++){
      |                     ~~^~~~~~~~~~~~~
bridge.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < diff.size()-1; i++)
      |                         ~~^~~~~~~~~~~~~~~

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