oj.uz

답안 #689395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689395 2023-01-28T11:53:12 Z thienbao1602 Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 468 KB 
#include    <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
using namespace std;

const ll INF = 1e9 + 1;

int n, K;
ll lSum = 0, rSum = 0, cur = 0;
priority_queue<ll> lStore;
priority_queue<ll, vector<ll>, greater<ll>> rStore;

bool cmp(pair<ll, ll>& x, pair<ll, ll>& y)
{
    return x.fi + x.se < y.fi + y.se;
}

void add(ll x)
{
    ll median = (lStore.empty() ? INF : lStore.top());
    if (x <= median)
    {
        lStore.push(x);
        lSum += x;
    } else
    {
        rStore.push(x);
        rSum += x;
    }

    if (sz(lStore) > 1 + sz(rStore))
    {
        ll tmp = lStore.top();
        lStore.pop();
        rStore.push(tmp);
        lSum -= tmp, rSum += tmp;
    }

    if (sz(lStore) < sz(rStore))
    {
        ll tmp = rStore.top();
        rStore.pop();
        lStore.push(tmp);
        lSum += tmp, rSum -= tmp;
    }
}

void solve()
{
    cin >> K >> n;
    vector<pair<ll, ll>> a;
    for(int i=0; i<n; i++)
    {
        ll x, y;
        char P, Q;
        cin >> P >> x >> Q >> y;
        if (P == Q) cur += abs(x - y);
         else a.push_back({x, y});
    }

    n = a.size(), cur += n;
    sort(a.begin(), a.end(), cmp);

    vector<ll> pref(n, 0);
    for(int i=0; i<n; i++)
    {
        add(a[i].fi);
        add(a[i].se);
        pref[i] = rSum - lSum;
    }


    ll ret = pref[n - 1];
    if (K == 2)
    {
        while(!lStore.empty()) lStore.pop();
        while(!rStore.empty()) rStore.pop();

        lSum = rSum = 0;
        vector<ll> suf(n, 0);
        for(int i=n-1; i>0; i--)
        {
            add(a[i].fi), add(a[i].se);
            ret = min(ret, pref[i - 1] + rSum - lSum);
        }
    }
    cout << ret + cur;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -