Submission #668725

#	Time	Username	Problem	Language	Result	Execution time	Memory
668725		ljuba	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	131 ms	8784 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x); cerr << "\033[0m";
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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

    ll ans = 0;

    vpll v;

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

        if(a == b) {
            ans += abs(x - y);
        } else {
            v.pb({x, y});
            ++ans;
        }
    }

    sort(all(v), [](pll a, pll b) {
        return a.fi + a.se < b.fi + b.se;
    });

    dbg(v);

    priority_queue<ll> levi;
    priority_queue<ll, vll, greater<>> desni;

    ll lsum = 0, rsum = 0;

    auto insert = [&](ll x) {
        levi.push(x);
        lsum += x;

        while(sz(levi) > sz(desni)) {
            ll naj = levi.top();
            levi.pop();

            lsum -= naj;
            rsum += naj;
            desni.push(naj);
        }

        //sz(levi) <= sz(desni)

        while(sz(levi) < sz(desni)) {
            ll naj =  desni.top();
            desni.pop();

            rsum -= naj;
            lsum += naj;
            levi.push(naj);
        }
    };

    auto obrisi = [&]() {
        while(sz(levi)) levi.pop();
        while(sz(desni)) desni.pop();
        lsum = 0;
        rsum = 0;
    };

    n = sz(v);
    vll pref(n + 2), suf(n + 2);

    for(int i = 1; i <= n; ++i) {
        auto p = v[i - 1];
        insert(p.fi);
        insert(p.se);

        pref[i] = rsum - lsum;
    }

    obrisi();

    for(int i = n; i >= 1; --i) {
        auto p = v[i - 1];
        insert(p.fi);
        insert(p.se);

        dbg(p, rsum, lsum);

        suf[i] = rsum - lsum;
    }

    ll dodaj = pref[n];

    if(k == 2) {
        for(int i = 1; i <= n; ++i) {
            ckmin(dodaj, pref[i] + suf[i + 1]);
        }
    } else {
        dodaj = pref[n];
    }

    dbg(dodaj);

    ans += dodaj;

    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

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