Submission #1246177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246177		tochika	Palembang Bridges (APIO15_bridge)	C++20	49 / 100	14 ms	2744 KiB

bridge

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

#define IN "iii.txt"
#define OUT "ooo.txt"
#define MULTI_TEST 0

lint l = 0, r = 0;
priority_queue<lint> under;
priority_queue<lint, vector<lint>, greater<lint>> above;

void add(lint x) {
    int med = (under.size() ? under.top() : 1000000001);

    if (x <= med) {
        under.push(x);
        l += x;
    }

    else {
        above.push(x);
        r += x;
    }

    if (above.size() + 1 < under.size()) {
        int t = under.top();
        under.pop();

        above.push(t);
        r += t;
        l -= t;
    }

    else if (under.size() < above.size()) {
        int t = above.top();
        above.pop();

        under.push(t);
        r -= t;
        l += t;
    }
}

void solve() {
    int k, n;
    cin >> k >> n;

    lint cnt = 0;
    vector<pair<lint, lint>> v = {{0LL, 0LL}};
    vector<lint> pf(10001, 0);

    for (int i = 0; i < n; i++) {
        char a, b;
        lint x, y;

        cin >> a >> x >> b >> y;

        if (a == b)
            cnt += abs(x - y);

        else v.push_back({x, y});
    }

    sort(v.begin(), v.end(), [&](pair<lint, lint>& m1, pair<lint, lint>& m2){
         return m1.first + m1.second < m2.first + m2.second;
    });

    n = v.size() - 1;
    cnt += n;

    l = r = 0;

    for (int i = 1; i <= n; i++) {
        add(v[i].first);
        add(v[i].second);

        pf[i] = r - l;
    }

    lint ans = pf[n];

    if (k == 2) {
        while (under.size()) under.pop();
        while (above.size()) above.pop();

        l = r = 0;

        for (int i = n; i > 0; i--) {
            add(v[i].first);
            add(v[i].second);

            ans = min(ans, r - l + pf[i - 1]);
        }
    }

    cout << ans + cnt;
}

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

    if (fopen(IN, "r")) {
        freopen(IN, "r", stdin);
        freopen(OUT, "w", stdout);
    }

    int t = 1;
    if (MULTI_TEST) {
        cin >> t;
    }

    for (int i = 1; i <= t; i++) {
        solve();
        cout << '\n';
    }

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

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