oj.uz

답안 #933106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933106 2024-02-25T04:19:26 Z sleepntsheep 학교 설립 (IZhO13_school) C++17
100 / 100
 298 ms 30116 KB 
#include<stdio.h>
#include<utility>
#include<set>
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 500005
int n,m,s,o[N],a[N],b[N],f[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,im,is,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()));
        }
    }

    for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
    printf("%lld",z);
}

Compilation message

school.cpp: In function 'void sort(int*, int, int)':
school.cpp:9:8: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
    9 |        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:9:161: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
    9 |        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:47:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |     ^~~
school.cpp:47:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   47 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |                           ^~~
school.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     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:18:55: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 5 ms 6748 KB Output is correct
10 Correct 3 ms 6744 KB Output is correct
11 Correct 4 ms 7000 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 19 ms 8376 KB Output is correct
14 Correct 56 ms 13484 KB Output is correct
15 Correct 122 ms 21336 KB Output is correct
16 Correct 225 ms 22356 KB Output is correct
17 Correct 207 ms 23140 KB Output is correct
18 Correct 201 ms 24660 KB Output is correct
19 Correct 252 ms 26596 KB Output is correct
20 Correct 298 ms 30116 KB Output is correct