Submission #933107

#	Time	Username	Problem	Language	Result	Execution time	Memory
933107		sleepntsheep	Schools (IZhO13_school)	C++17	100 / 100	336 ms	29160 KiB

school

#include<stdio.h>
#include<utility>
#include<set>
unsigned X=12345;int rand_(){return(X*=3)/2;}
int (*compar)(int,int);
void sort(int*aa,int l,int r){
    while(l<r){int i=l,j=l,k=r,tmp,p=aa[l+rand_()%(r-l)];
       while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}}

#define N 500005
int n,m,s,o[N],a[N],b[N];long long z;
int bya(int i,int j){return a[i]<a[j]?1:a[i]>a[j]?-1:0;}

std::set<std::pair<int,int>>cm,cf,cf_nm;

int main(){
    scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i;
    compar=bya;sort(o,0,n);

    for(int i=0;i<m;++i)cm.insert({b[o[i]]-a[o[i]],i}),z+=a[o[i]];
    for(int i=m;i<n;++i)cf.insert({b[o[i]],i}), cf_nm.insert({a[o[i]],i});

    for(int j=0;j<s;++j)
    {
        if(cm.empty()||(cf.size()&&cf.rbegin()->first>=cm.rbegin()->first+cf_nm.rbegin()->first))
        {
            int i=cf.rbegin()->second;
            cf_nm.erase({a[o[i]],i});
            cf.erase(std::prev(cf.end()));
            z+=b[o[i]];
        }
        else
        {
            int i=cm.rbegin()->second;
            cm.erase(std::prev(cm.end()));
            int nm=cf_nm.rbegin()->second;
            z+=b[o[i]]-a[o[i]]+a[o[nm]];
            cm.insert({b[o[nm]]-a[o[nm]],nm});
            cf.erase({b[o[nm]],nm});
            cf_nm.erase(std::prev(cf_nm.end()));
        }
    }

    printf("%lld",z);
}

Compilation message (stderr)

school.cpp: In function 'void sort(int*, int, int)':
school.cpp:8:8: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
    8 |        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}}
      |        ^~~~~
school.cpp:8:161: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
    8 |        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}}
      |                                                                                                                                                                 ^~~~
school.cpp: In function 'int main()':
school.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:17:55: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i;
      |                                                  ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100