제출 #106657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106657		popovicirobert	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	580 ms	14740 KiB

bridge

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;

inline ll getmin(ll a, ll b) {
    return a < b ? a : b;
}

inline void solve(vector < pair <int, int> > &arr, vector <ll> &sol) {
    int sz = arr.size();
    sol.resize(sz);

    multiset <int> mst1, mst2;
    ll sum1 = 0, sum2 = 0;

    for(int i = 0; i < sz; i++) {
        mst2.insert(arr[i].first);
        sum2 += arr[i].first;
        mst2.insert(arr[i].second);
        sum2 += arr[i].second;

        while(mst1.size() < i + 1) {
            mst1.insert(*mst2.begin());
            sum1 += *mst2.begin();
            sum2 -= *mst2.begin();
            mst2.erase(mst2.begin());
        }

        while(*prev(mst1.end()) > *mst2.begin()) {
            int a = *prev(mst1.end()), b = *mst2.begin();
            mst1.erase(mst1.find(a));
            mst1.insert(b);
            mst2.erase(mst2.find(b));
            mst2.insert(a);
            sum1 += b - a;
            sum2 += a - b;
        }

        int cur = *prev(mst1.end());
        sol[i] = 1LL * mst1.size() * cur - sum1 + sum2 - 1LL * mst2.size() * cur;

    }

}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> k >> n;

    vector < pair <int, int> > arr;
    ll ans = 0;
    for(i = 1; i <= n; i++) {
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if(x > y) {
            swap(x, y);
        }
        if(a != b) {
            arr.push_back({x, y});
        }
        else {
            ans += y - x;
        }
    }

    sort(arr.begin(), arr.end(), [&](const pair <int, int> &a, const pair <int, int> &b) {

            return a.first + a.second < b.first + b.second;

        });

    if(arr.size() == 0) {
        cout << ans;
        return 0;
    }

    if(k == 1) {
        vector <int> vals;
        ll tot = 0;
        for(auto it : arr) {
            vals.push_back(it.first);
            vals.push_back(it.second);
            tot += it.first + it.second;
        }
        sort(vals.begin(), vals.end());
        int sz = arr.size();
        ll mn = INF, sum = 0;
        for(i = 0; i < 2 * sz; i++) {
            mn = getmin(mn, 1LL * vals[i] * i - sum + (tot - sum) - 1LL * vals[i] * (2 * sz - i));
            sum += vals[i];
        }
        cout << ans + mn + sz;
        return 0;
    }

    vector <ll> sol_l, sol_r;
    solve(arr, sol_l);
    reverse(arr.begin(), arr.end());
    solve(arr, sol_r);

    int sz = arr.size();
    ll mn = getmin(sol_l[sz - 1], sol_r[sz - 1]);
    for(int i = 0; i < sz - 1; i++) {
        mn = getmin(mn, sol_l[i] + sol_r[sz - i - 2]);
    }

    cout << ans + mn + sz;

    //cin.close();
    //cout.close();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void solve(std::vector<std::pair<int, int> >&, std::vector<long long int>&)':
bridge.cpp:29:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(mst1.size() < i + 1) {
               ~~~~~~~~~~~~^~~~~~~

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