Submission #47524

#	Time	Username	Problem	Language	Result	Execution time	Memory
47524		ngkan146	Schools (IZhO13_school)	C++11	100 / 100	192 ms	41936 KiB

school

// khanh best
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct school{
   ll m, s, id;
   school(ll m=0,ll s=0,ll id=0): m(m), s(s), id(id) {}
};
ll N,M,S;
school a[300005];
ll sum;
bool cmp(school x,school y){
   return x.m - x.s < y.m - y.s;
}
struct cmpS{
   bool operator ()(school x,school y){
      return x.s > y.s;
   }
};
struct cmpM{
   bool operator ()(school x,school y){
      return x.m - x.s > y.m - y.s;
   }
};
struct cmpM2{
   bool operator ()(school x,school y){
      return x.m > y.m;
   }
};
priority_queue <school,vector<school>,cmpS> pqS;
priority_queue <school,vector<school>,cmpM> pqM;
priority_queue <school,vector<school>,cmpM2> pqM2;
bool usedM[300005];
int main(){
   scanf("%lld %lld %lld",&N,&M,&S);
   for(int i=1;i<=N;i++)
      scanf("%lld %lld",&a[i].m,&a[i].s),
      sum += a[i].m,
      a[i].id = i;
   sort(a+1,a+N+1,cmp);
   for(int i=1;i<=S;i++)
      sum -= (a[i].m - a[i].s);
   for(int i=1;i<=S;i++)
      pqS.push(a[i]);
   for(int i=S+1;i<=N;i++)
      pqM.push(a[i]),
      pqM2.push(a[i]);
   ll zero = N - M - S;

   while(zero--){
      ll canS = pqS.top().s;
      while(usedM[pqM.top().id]) pqM.pop();
      canS += pqM.top().m - pqM.top().s;

      while(usedM[pqM2.top().id]) pqM2.pop();
      ll canM = pqM2.top().m;
      if (canS < canM){
         usedM[pqM.top().id] = 1;
         sum -= canS;
         pqS.pop();
         pqS.push(pqM.top());
         pqM.pop();
      }
      else{
         usedM[pqM2.top().id] = 1;
         sum -= canM;
         pqM2.pop();
      }
   }
   cout << sum;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld %lld %lld",&N,&M,&S);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld %lld",&a[i].m,&a[i].s),
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       sum += a[i].m,
       ~~~~~~~~~~~~~^~
       a[i].id = i;
       ~~~~~~~~~~~

• Subtask 1: 100 / 100