Submission #208323

#TimeUsernameProblemLanguageResultExecution timeMemory
208323mohamedsobhi777Schools (IZhO13_school)C++14
25 / 100
347 ms12920 KiB
#include<bits/stdc++.h> 
 
using namespace std ;

const int N = 1e6 + 7 , mod = 998244353; 

long long n   , A , B; 
long long a[N] , b[N] ; 
long long ans ; 
int gA , gB ; 

priority_queue<pair< long long , int > > q1 , q2 ;

void clear1(){
        if(q1.size() > A){
            gA = q1.size() -A ; 
            priority_queue<long long> aux ; 
            while(q1.size()){
                aux.push(-a[q1.top().second]) ; 
                q1.pop() ; 
            }
            while(gA--){
                ans+=aux.top() ; 
                aux.pop();
            }
        }
        if(q2.size() > B){
            gB = q2.size() -B ; 
            priority_queue<long long> aux ; 
            while(q2.size()){
                aux.push(-b[q2.top().second]) ; 
                q2.pop() ; 
            }
            while(gB--){
                ans+=aux.top() ; 
                aux.pop();
            }
        }
}

int main() 
{
   // freopen("in.in" , "r" , stdin) ; 
    cin>>n>>A>>B ; 
    for(int i = 0 ; i < n ; i++){
        cin>>a[i] >> b[i] ; 
        if(a[i]>=b[i]){
            q1.push({ b[i] -a[i],i });
        }
        else {
            q2.push({ a[i] - b[i] , i}) ; 
        }
        ans += max(a[i] , b[i] ) ;
    }

    if(q1.size() > A && q2.size() > B)
    {
        clear1();
    }

    while(q1.size()> A && q2.size() < B){

        ans+=q1.top().first ; 
        q2.push({a[q1.top().second] - b[q1.top().second] ,q1.top().second });
        q1.pop(); 
    }

    if(q1.size() > A){
        priority_queue<pair< pair<long long , long long > , int  > > aux1 ; 
        priority_queue< pair<long long , int >  >  aux2 ; 

        while(q1.size()) 
        {
            aux1.push( { {  b[q1.top().second] - a[q1.top().second], b[q1.top().second]} ,q1.top().second });
            q1.pop();
        }
        while(q2.size())
        {
            aux2.push({-b[q2.top().second] , q2.top().second });
            q2.pop();
        }
        while(aux1.size() > A  && aux1.top().first.second>=-aux2.top().first ) {
            ans+=aux2.top().first;        
            ans+=aux1.top().first.first;
            aux2.pop();
            aux2.push({-aux1.top().first.second ,aux1.top().second });
            aux1.pop();
        }
        for(int i = 0 ; i < A ; i++)
            aux1.pop();
        while(aux1.size()){
            ans-=a[aux1.top().second];
            aux1.pop();
        }
    }
    while(q2.size()> B){
        ans+=q2.top().first ; 
        q1.push({b[q2.top().second] - a[q2.top().second] , q2.top().second}) ;
        q2.pop(); 
    }


    if(q2.size() > B){
        priority_queue<pair< pair<long long , long long > , int  > > aux1 ; 
        priority_queue< pair<long long , int >  >  aux2 ; 

        while(q2.size()) 
        {
            aux1.push( { {  a[q2.top().second] - b[q2.top().second], a[q2.top().second]} ,q2.top().second });
            q2.pop();
        }
        while(q1.size())
        {
            aux2.push({-a[q1.top().second] , q1.top().second });
            q1.pop();
        }
        while(aux1.size() > B  && aux1.top().first.second>=-aux2.top().first ) {
            ans+=aux2.top().first;        
            ans+=aux1.top().first.first;
            aux2.pop();
            aux2.push({-aux1.top().first.second ,aux1.top().second });
            aux1.pop();
        }
        for(int i = 0 ; i < B ; i++)
            aux1.pop();
        while(aux1.size()){
            ans-=b[aux1.top().second];
            aux1.pop();
        }
    }

    clear1();

    cout<<ans; 
    return 0 ;  
}

Compilation message (stderr)

school.cpp: In function 'void clear1()':
school.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q1.size() > A){
            ~~~~~~~~~~^~~
school.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q2.size() > B){
            ~~~~~~~~~~^~~
school.cpp: In function 'int main()':
school.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(q1.size() > A && q2.size() > B)
        ~~~~~~~~~~^~~
school.cpp:56:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(q1.size() > A && q2.size() > B)
                         ~~~~~~~~~~^~~
school.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(q1.size()> A && q2.size() < B){
           ~~~~~~~~~^~~
school.cpp:61:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(q1.size()> A && q2.size() < B){
                           ~~~~~~~~~~^~~
school.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(q1.size() > A){
        ~~~~~~~~~~^~~
school.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(aux1.size() > A  && aux1.top().first.second>=-aux2.top().first ) {
               ~~~~~~~~~~~~^~~
school.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(q2.size()> B){
           ~~~~~~~~~^~~
school.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(q2.size() > B){
        ~~~~~~~~~~^~~
school.cpp:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(aux1.size() > B  && aux1.top().first.second>=-aux2.top().first ) {
               ~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...