Submission #1017810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017810		aufan	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	67 ms	7480 KiB

bridge

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
 
using namespace std;
 
const int inff = 1e18;
 
int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int k, n;
        cin >> k >> n;
 
        int ans = 0;
        vector<int> a, b;
        for (int i = 0; i < n; i++) {
                char p, q;
                int s, t;
                cin >> p >> s >> q >> t;
 
                if (p == q) {
                        ans += abs(s - t);
                } else {
                        if (s > t) swap(s, t);
                        a.push_back(s);
                        b.push_back(t);
                }
        }
 
        if (k == 1) {
                int m = (int)a.size();
                vector<int> c;
                for (int i = 0; i < m; i++) {
                        c.push_back(a[i]);
                        c.push_back(b[i]);
                }
                sort(c.begin(), c.end());
                
                ans += m;
                for (int i = 0; i < 2 * m; i++) {
                        ans += abs(c[i] - c[m]);
                }
 
                cout << ans << '\n';
        } else if (k == 2) {
                int m = (int)a.size();
                vector<pair<int, int>> c;
                for (int i = 0; i < m; i++) {
                        c.push_back({a[i], b[i]});
                }
                sort(c.begin(), c.end(), [&](pair<int, int> x, pair<int, int> y) {
                        return x.fi + x.se < y.fi + y.se;
                });
 
                int sl = 0, sr = 0;
                vector<int> pref(m);
                priority_queue<int> le;
                priority_queue<int, vector<int>, greater<int>> ri;
                for (int i = 0; i < m; i++) {
                        auto [a, b] = c[i];
                        sl += a;
                        le.push(a);
                        sr += b;
                        ri.push(b);
                        while (le.top() > ri.top()) {
                                sr += le.top();
                                ri.push(le.top());
                                sl += ri.top();
                                le.push(ri.top());
                                sr -= ri.top();
                                ri.pop();
                                sl -= le.top();
                                le.pop();
                        }
 
                        pref[i] = ((i + 1) * le.top() - sl) + (sr - (i + 1) * le.top());
                }
 
                sl = sr = 0;
                while (!le.empty()) le.pop();
                while (!ri.empty()) ri.pop();
                vector<int> suf(m);
                for (int i = m - 1; i >= 0; i--) {
                        auto [a, b] = c[i];
                        sl += a;
                        le.push(a);
                        sr += b;
                        ri.push(b);
                        while (le.top() > ri.top()) {
                                sr += le.top();
                                ri.push(le.top());
                                sl += ri.top();
                                le.push(ri.top());
                                sr -= ri.top();
                                ri.pop();
                                sl -= le.top();
                                le.pop();
                        }
 
                        suf[i] = ((m - i) * le.top() - sl) + (sr - (m - i) * le.top());
                }
 
                int mn = inff;
                ans += m;
                for (int i = 0; i < m - 1; i++) mn = min(mn, pref[i] + suf[i + 1]);
                if (m == 0) mn = 0;     
                ans += mn;
 
                cout << ans << '\n';
        }
        
        return 0;
}

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