Submission #629014

#	Time	Username	Problem	Language	Result	Execution time	Memory
629014		Neos	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	102 ms	6308 KiB

bridge

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define MASK(x) 1ll << (x)

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

const int N = 1e6 + 7, oo = 1e9 + 7;

int n, k;
vector<ii> b;
ll lsum, rsum, pre[N];

bool cmp(ii x, ii y) {
    return (x.fi + x.se < y.fi + y.se);
}

priority_queue<int> mx;
priority_queue<int, vector<int>, greater<int>> mn;
void add(int x) {
    int med = (mn.empty() ? oo : mx.top());
    if (x <= med) lsum += x, mx.push(x);
    else mn.push(x), rsum += x;

    while (sz(mn) >= sz(mx)) {
        int nxt = mn.top(); mn.pop();
        rsum -= nxt; lsum += nxt; mx.push(nxt);
    }

    while (sz(mx) - 1 > sz(mn)) {
        int nxt = mx.top(); mx.pop();
        lsum -= nxt; rsum += nxt; mn.push(nxt);
    }
}

signed main() {
    fastIO;
    if (fopen("bridge.inp", "r")) {
        freopen("bridge.inp", "r", stdin);
        freopen("bridge.out", "w", stdout);
    }
    cin >> k >> n; ll ans = 0, same = 0;
    for (int i = 1, x1, y1; i <= n; i++) {
        char x, y; cin >> x >> x1 >> y >> y1;
        if (x == y) same += abs(y1 - x1); else b.pb({x1, y1});
    }

    sort(all(b), cmp);
    for (int i = 0; i < sz(b); i++) {
        add(b[i].fi); add(b[i].se);
        ans = pre[i] = rsum - lsum;
    }

    if (k == 2) {
        lsum = rsum = 0;
        while (!mn.empty()) mn.pop();
        while (!mx.empty()) mx.pop();

        for (int i = sz(b) - 1; i > 0; i--) {
            add(b[i].fi); add(b[i].se);
            minimize(ans, rsum - lsum + pre[i - 1]);
        }
    }
    cout << ans + same + sz(b);
}

Compilation message (stderr)

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

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