Submission #500856

#	Time	Username	Problem	Language	Result	Execution time	Memory
500856		Halogen	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	108 ms	8680 KiB

bridge

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

#define int long long
typedef pair<int, int> ii;

main() {
    int K, N; scanf("%lld %lld", &K, &N);
    int ans = 0;
    vector<pair<int, int> > lst;
    
    for (int i = 0; i < N; i++) {
        char c1, c2;
        int i1, i2;
        scanf(" %c %lld %c %lld", &c1, &i1, &c2, &i2);
        if (c1 == c2) ans += abs(i2 - i1);
        else lst.emplace_back(i1, i2);
    }

    sort(lst.begin(), lst.end(), [](ii i, ii j) {
        return i.first + i.second < j.first + j.second;
    });

    N = lst.size();

    int pre[N + 5], suf[N + 5];
    memset(pre, 0, sizeof(pre));
    memset(suf, 0, sizeof(suf));

    int left = 0, right = 0;
    priority_queue<int> l;
    priority_queue<int, vector<int>, greater<int> > r;

    for (int i = 0; i < N; i++) {
        r.push(lst[i].first); r.push(lst[i].second);
        right += lst[i].first + lst[i].second;
        while (l.size() < r.size() || r.top() < l.top()) {
            right -= r.top();
            left += r.top();
            l.push(r.top()); r.pop();
        }
        while (l.size() > r.size()) {
            right += l.top();
            left -= l.top();
            r.push(l.top()); l.pop();
        }

        pre[i] = right - r.size() * l.top() + l.top() * l.size() - left;
    }

    left = right = 0;
    while (!r.empty()) r.pop();
    while (!l.empty()) l.pop();

    for (int i = N - 1; i >= 0; --i) {
        r.push(lst[i].first); r.push(lst[i].second);
        right += lst[i].first + lst[i].second;
        while (l.size() < r.size() || r.top() < l.top()) {
            right -= r.top();
            left += r.top();
            l.push(r.top()); r.pop();
        }
        while (l.size() > r.size()) {
            right += l.top();
            left -= l.top();
            r.push(l.top()); l.pop();
        }

        suf[i] = right - r.size() * l.top() + l.top() * l.size() - left;
    }

    int mini = min(suf[0], pre[N - 1]);
    
    // for (int i = 0; i < N; i++)
    //     printf("%lld %lld\n", pre[i], suf[i]);

    if (K == 1) {
        printf("%lld\n", mini + N + ans);
        return 0;
    }

    for (int i = 0; i < N - 1; i++)
        mini = min(mini, suf[i + 1] + pre[i]);

    printf("%lld\n", mini + N + ans);
}

Compilation message (stderr)

bridge.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main() {
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     int K, N; scanf("%lld %lld", &K, &N);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %c %lld %c %lld", &c1, &i1, &c2, &i2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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