Submission #699462

#	Time	Username	Problem	Language	Result	Execution time	Memory
699462		nguyentunglam	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	96 ms	5988 KiB

bridge

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
long long sum, pref[N], suff[N];
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int> > q2;
void balance() {
    while (q1.top() > q2.top()) {
        int x = q1.top(), y = q2.top();
        q1.pop(); q2.pop();
        sum += 2 * x; sum -= 2 * y;
        q1.push(y); q2.push(x);
    }
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int k, n, m = 0; cin >> k >> n;
    long long sameside = 0;
    for(int i = 1; i <= n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if (p == q) sameside += abs(s - t);
        else {
            if (s > t) swap(s, t);
            a[++m] = make_pair(s, t);
            sameside++;
        }
    }
    sort(a + 1, a + m + 1, [] (const ii &x, const ii &y) {
         return x.fi + x.se < y.fi + y.se;
         });

    for(int i = 1; i <= m; i++) {
        q1.push(a[i].fi); sum -= a[i].fi;
        q2.push(a[i].se); sum += a[i].se;
        balance();
        pref[i] = sum;
    }
    if (k == 1) return cout << pref[m] + sameside, 0;
    sum = 0;
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    for(int i = m; i >= 1; i--) {
        q1.push(a[i].fi); sum -= a[i].fi;
        q2.push(a[i].se); sum += a[i].se;
        balance();
        suff[i] = sum;
    }
    long long res = pref[m];
    for(int i = 2; i <= m; i++) res = min(res, suff[i] + pref[i - 1]);
    cout << res + sameside;
}

Compilation message (stderr)

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

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