Submission #338543

#	Time	Username	Problem	Language	Result	Execution time	Memory
338543		shahriarkhan	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	106 ms	5728 KiB

bridge

#include <bits/stdc++.h>
using namespace std ;

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

priority_queue<int> l ;

priority_queue<int , vector<int> , greater<int> > r ;

long long lsum , rsum ;

void append(int x)
{
    int median = (l.size() ? l.top() : 1000000001) ;
    if(x <= median)
    {
        l.push(x) ;
        lsum += x ;
    }
    else
    {
        r.push(x) ;
        rsum += x ;
    }

    if(r.size() + 1 < l.size())
    {
        int next = l.top() ;
        l.pop() ;
        r.push(next) ;
        lsum -= next ;
        rsum += next ;
    }
    else if(l.size() < r.size())
    {
        int next = r.top() ;
        r.pop() ;
        l.push(next) ;
        rsum -= next ;
        lsum += next ;
    }
}

long long pref[100001] ;

int main()
{
    int k , n ;
    scanf("%d%d",&k,&n) ;
    long long same_side = 0 ;
    vector<pair<int,int> > v = {{0,0}} ;
    for(int i = 0 ; i < n ; ++i)
    {
        char a , b ;
        int x , y ;
        scanf(" %c%d %c%d",&a,&x,&b,&y) ;
        if(a==b) same_side += abs(x-y) ;
        else v.push_back({x,y}) ;
    }
    sort(v.begin(),v.end(),cmp) ;
    n = v.size() - 1 ;
    same_side += n ;
    lsum = rsum = 0 ;
    for(int i = 1 ; i <= n ; ++i)
    {
        append(v[i].first) ;
        append(v[i].second) ;
        pref[i] = rsum - lsum ;
    }
    long long ans = pref[n] ;
    if(k==2)
    {
        while(!l.empty()) l.pop() ;
        while(!r.empty()) r.pop() ;
        lsum = rsum = 0 ;
        for(int i = n ; i >= 1 ; --i)
        {
            append(v[i].first) ;
            append(v[i].second) ;
            ans = min(ans , rsum - lsum + pref[i-1]) ;
        }
    }
    printf("%lld\n",same_side + ans) ;
    return 0 ;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d%d",&k,&n) ;
      |     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf(" %c%d %c%d",&a,&x,&b,&y) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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