Submission #527845

#	Time	Username	Problem	Language	Result	Execution time	Memory
527845		Deepesson	Schools (IZhO13_school)	C++17	80 / 100	102 ms	17020 KiB

school

#include <bits/stdc++.h>
#define MAX 205000
using ll = long long;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plp;
int sk1[MAX],sk2[MAX];
int n,a,b;
 
int main()
{
    scanf("%d %d %d",&n,&a,&b);
    std::vector<pll> vec;
    for(int i=0;i!=n;++i){
        int c,d;
        scanf("%d %d",&c,&d);
        vec.push_back({c,d});
    }
    std::sort(vec.begin(),vec.end(),std::greater<pll>());
    for(int i=0;i!=n;++i){
        sk1[i]=vec[i].first;
        sk2[i]=vec[i].second;
    }
    bool pegou[n]={};
    int cur=a;
    long long s=0;
    for(int i=0;i!=a;++i){
        s+=sk1[i];
        pegou[i]=true;
    }
    std::priority_queue<pll> queue,novasskills,addo;
    for(int i=0;i!=a;++i){
        long long delta = sk2[i]-sk1[i];
        queue.push({delta,i});
    }
    for(int i=a;i!=n;++i){
        novasskills.push({sk1[i],i});
        addo.push({sk2[i],i});
    }
    for(int i=0;i!=b;++i){
        long long bonus=0;
        while(novasskills.size()){
            if(pegou[novasskills.top().second]){
                novasskills.pop();
            }else {bonus=novasskills.top().first;break;}
        }
        if(queue.size()){
            bonus+=queue.top().first;
        }else bonus=-(1e9+7);
        long long add=0;
        while(addo.size()){
            if(pegou[addo.top().second]){
                addo.pop();
            }else {add=addo.top().first;break;}
        }
        if(bonus>add){
            queue.pop();
            queue.push({sk2[novasskills.top().second]-sk1[novasskills.top().second],novasskills.top().second});
            pegou[novasskills.top().second]=true;
            novasskills.pop();
            s+=bonus;
 
        }else {
            s+=add;
            pegou[addo.top().second]=true;
            addo.pop();
        }
    }
    std::cout<<s<<"\n";
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:24:9: warning: unused variable 'cur' [-Wunused-variable]
   24 |     int cur=a;
      |         ^~~
school.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d %d",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
school.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d %d",&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 80 / 100