# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
933101 | sleepntsheep | Schools (IZhO13_school) | C++17 | 1 ms | 792 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<utility>
#include<set>
#include<queue>
int hi(int a,int b){return a>b?a:b;}
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 505
int n,m,s,o[N],o2[N],a[N],b[N],f[N];long long z,lazy;
int bya(int i,int j){return a[i]<a[j]?1:a[i]>a[j]?-1:0;}
int nm;
std::multiset<std::pair<int,int>>cm,cf,im,is;
int inm(int i)
{
return im.find({a[o[i]],i})!=im.end();
}
int ins(int i)
{
return is.find({b[o[i]],i})!=is.end();
}
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,o2[i]=i;
compar=bya;sort(o,0,n);
for(int i=0;i<m;++i)cm.insert({b[o[i]]-a[o[i]],i}),im.insert({a[o[i]],i});
for(int i=m;i<n;++i)cf.insert({b[o[i]],i});
nm=m;
for(;is.size()<s;)
{
while(nm+1<n&&(inm(nm)||ins(nm)))++nm;
if(cm.empty()||(cf.size()&&cf.rbegin()->first>=cm.rbegin()->first+a[o[nm]]))
{
is.insert(*cf.rbegin());
cf.erase(std::prev(cf.end()));
}
else
{
int i=cm.rbegin()->second;
is.insert({b[o[i]],i});
cm.erase(std::prev(cm.end()));
im.erase(im.find({a[o[i]],i}));
im.insert({a[o[nm]],nm});
cm.insert({b[o[nm]]-a[o[nm]],nm});
}
}
for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
printf("%lld",z);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |