Submission #435301

#	Time	Username	Problem	Language	Result	Execution time	Memory
435301		iANikzad	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	109 ms	7976 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 1;
const int mlog = 20;
const int SQ = 400;

int ls, rs;
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;

int pref[maxn];

bool cmp(pii a, pii b) { return a.first + a.second < b.first + b.second; }

void add(int x)
{
    int median = (lpq.size() ? lpq.top() : +INF);

    if (x <= median)
    {
        lpq.push(x);
        ls += x;
    } else  {
        rpq.push(x);
        rs += x;
    }


    if (rpq.size() + 1 < lpq.size())
    {
        int nxt = lpq.top();
        lpq.pop(); rpq.push(nxt);
        ls -= nxt; rs += nxt;

    } else if (lpq.size() < rpq.size())
    {
        int nxt = rpq.top();
        rpq.pop();
        lpq.push(nxt);
        rs -= nxt; ls += nxt;
    }
}

int32_t main()
{
    FAST;

    int n, k;
    cin >> k >> n;

    int ham = 0;

    vector<pii> vec = {{0, 0}};

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

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

    sort(all(vec), cmp);

    n = vec.size() - 1;
    ham += n;

    ls = rs = 0;
    for(int i = 1; i <= n; i++)
    {
        add(vec[i].F); add(vec[i].S);
        pref[i] = rs - ls;
    }

    int ans = pref[n];
    if(k == 2)
    {
        while(lpq.size()) lpq.pop();
        while(rpq.size()) rpq.pop();

        ls = rs = 0;
        for(int i = n; i; i--)
        {
            add(vec[i].F); add(vec[i].S);
            ans = min(ans, rs - ls + pref[i - 1]);
        }
    }

    cout << ham + ans << "\n";

    return 0;
}

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