Submission #387266

#	Time	Username	Problem	Language	Result	Execution time	Memory
387266		jjang36524	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	190 ms	8828 KiB

bridge

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <stdlib.h>
using namespace std;
#define int long long
priority_queue<int>l;
priority_queue<int,vector<int>,greater<int>>r;
int lc=0;
void ins(int n)
{
    int ml=l.size()?l.top():(1<<30);
    if(n<ml)
    {
        lc+=n;
        l.push(n);
        if(l.size()-1>r.size())
        {
            lc-=l.top();
            r.push(l.top());
            l.pop();
        }
    }
    else
    {
        r.push(n);
        if(r.size()>l.size())
        {
            lc+=r.top();
            l.push(r.top());
            r.pop();
        }
    }
}
bool cmp(pair<int,int>a,pair<int,int>b)
{
    return a.first+a.second<b.first+b.second;
}
signed main()
{
    int N,K;
    cin >> K >> N;
    int i;
    int ans=0;
    vector<pair<int,int>>x;
    for(i=0;i<N;i++)
    {
        char a,b;
        int c,d;
        cin >> a >> c >> b >> d;
        if(a==b)
            ans+=max(c,d)-min(c,d);
        else
            x.push_back({min(c,d),max(c,d)});
    }
    N=x.size();
    sort(x.begin(),x.end(),cmp);
    vector<int>la;
    vector<int>ra;
    la.push_back(0);
    int totsu=0;
    for(i=0;i<N;i++)
    {
        ins(x[i].first);
        ins(x[i].second);
        totsu+=x[i].first+x[i].second;
        la.push_back(totsu-2*lc);
    }
    ra.push_back(0);
    totsu=0;
    lc=0;
    while(l.size())
        l.pop();
    while(r.size())
        r.pop();
    for(i=N-1;i>=0;i--)
    {
        ins(x[i].first);
        ins(x[i].second);
        totsu+=x[i].first+x[i].second;
        int mid=l.top();
        ra.push_back(totsu-2*lc);
    }
    int an=1LL<<60;
    for(i=0;i<=N;i++)
    {
        if(K==2)
            an=min(an,la[i]+ra[N-i]);
        else
            an=la[N];
    }
    cout << ans+an+N;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:83:13: warning: unused variable 'mid' [-Wunused-variable]
   83 |         int mid=l.top();
      |             ^~~

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