제출 #563199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563199		piOOE	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	331 ms	14796 KiB

bridge

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 100002;
const int mod = 998244353;
const ld eps = 1e-9;

int A[N], B[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    cin >> k >> n;
    ll ans = 0, additional = 0;
    for (int i = 0; i < n; ++i) {
        string s1, s2;
        int x, y;
        cin >> s1 >> x >> s2 >> y;
        if (x > y) swap(x, y);
        if (s1 == s2) {
            additional += y - x;
            --i, --n;
            continue;
        }
        additional += 1;
        A[i] = x, B[i] = y;
    }
    if (n == 0) {
        cout << additional;
        return 0;
    }
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [](int i, int j) {
        return A[i] + B[i] < A[j] + B[j];
    });
    //note that we choose to go to L if A + B <= L + R, and to R otherwise
    multiset<int> L, R;
    ll sum[2] = {0, 0};
    int mid = 0;
    auto add = [&L, &R, &mid, &sum](int x) {
        if (x < mid) {
            L.insert(x);
            sum[0] += x;
        } else {
            R.insert(x);
            sum[1] += x;
        }
        if (sz(L) > sz(R)) {
            int v = *L.rbegin();
            L.extract(v);
            sum[0] -= v;
            sum[1] += v;
            mid = v;
            R.insert(v);
        } else if (sz(R) > sz(L)) {
            int v = *R.begin();
            R.erase(R.begin());
            sum[1] -= v;
            sum[0] += v;
            mid = v;
            L.insert(v);
        }
    };
    vector<ll> pref(n), suf(n);
    for (int j = 0; j < n; ++j) {
        int i = ord[j];
        add(A[i]);
        add(B[i]);
        pref[j] = (mid * (ll) sz(L) - sum[0]) + (sum[1] - (mid * (ll) sz(R)));
    }
    L.clear(), R.clear(), sum[0] = sum[1] = mid = 0;
    for (int j = n - 1; j > -1; --j) {
        int i = ord[j];
        add(A[i]);
        add(B[i]);
        suf[j] = (mid * (ll) sz(L) - sum[0]) + (sum[1] - (mid * (ll) sz(R)));
    }
    ans = suf[0];
    if (k == 2) {
        for (int i = 1; i < n; ++i) {
            ckmn(ans, pref[i - 1] + suf[i]);
        }
    }
    cout << ans + additional;
    return 0;
}

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