oj.uz

Submission #527846

# Submission time Handle Problem Language Result Execution time Memory
527846 2022-02-18T13:46:00 Z Deepesson Schools (IZhO13_school) C++17
100 / 100
 126 ms 22556 KB 
#include <bits/stdc++.h>
#define MAX 305000
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

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 13 ms 2152 KB Output is correct
14 Correct 31 ms 7356 KB Output is correct
15 Correct 68 ms 13676 KB Output is correct
16 Correct 102 ms 15028 KB Output is correct
17 Correct 99 ms 18172 KB Output is correct
18 Correct 126 ms 18916 KB Output is correct
19 Correct 106 ms 19340 KB Output is correct
20 Correct 125 ms 22556 KB Output is correct