Submission #236693

#	Time	Username	Problem	Language	Result	Execution time	Memory
236693		DS007	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	329 ms	15336 KiB

bridge

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

const int N = 1e5;
int n, k;
vector<pair<int, int>> v;
int l[N], r[N];

template<class T>
void solve(T it, T end, int *result) {
    multiset<int> ls, mr;
    int sls = 0, smr = 0, c = 0;

    while (it != end) {
        ls.insert(it->first);
        sls += it->first;
        mr.insert(it->second);
        smr += it->second;

        if (*ls.rbegin() > *mr.begin()) {
            sls += *mr.begin() - *ls.rbegin();
            smr += *ls.rbegin() - *mr.begin();
            ls.insert(*mr.begin());
            mr.insert(*ls.rbegin());
            ls.erase(ls.find(*ls.rbegin()));
            mr.erase(mr.find(*mr.begin()));
        }

        result[c++] = smr - sls;
        it++;
    }
}

int solveTestCase() {
    cin >> k >> n;

    int temp = 0;
    for (int i = 0; i < n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if (p == q)
            temp += abs(t - s);
        else
            v.emplace_back(s, t);
    }

    n = v.size();
    sort(v.begin(), v.end(), [](auto &p1, auto &p2) {
       return p1.first + p1.second < p2.first + p2.second;
    });

    solve(v.begin(), v.end(), l);
    solve(v.rbegin(), v.rend(), r);

    int ans = temp + n + min(l[n - 1], r[n - 1]);
    if (k == 1)
        return cout << ans, 0;

    for (int i = 0; i < n - 1; i++)
        ans = min(ans, temp + n + l[i] + r[n - 2 - i]);
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message (stderr)

bridge.cpp: In function 'long long int solveTestCase()':
bridge.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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