Submission #1225630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225630		fermat	Schools (IZhO13_school)	C++20	100 / 100	150 ms	19340 KiB

school

#include <bits/stdc++.h>

#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define int long long

using namespace std;

const int N = 3e5 + 5;

int n, x, y;

pair <int, int> a[N];

long long ans;

priority_queue < pair <int, int> > q1, q2; 

set <int> st;

main()
{
 cin >> n >> x >> y;
 
 for (int i = 1; i <= n; i++)
 {
  scanf("%d%d", &a[i].fr, &a[i].sc);
 }
 sort( a + 1, a + n + 1, greater < pair <int, int> >() );
 
 for (int i = 1; i <= x; i++)
  ans += a[i].fr, q1.push( mk(-a[i].fr + a[i].sc, i) );
  
 for (int i = x + 1; i <= n; i++)
  q2.push( mk(a[i].sc, i) ), st.insert(i);
 
 while(y--)
 {
  while (!q2.empty() && !st.count(q2.top().sc) )
   q2.pop();
   
  if ( q2.empty() || (!q1.empty() && q1.top().fr + a[*st.begin()].fr > q2.top().fr ) )
  {
   ans += q1.top().fr + a[*st.begin()].fr;
   q1.pop();
   q1.push( mk( -a[*st.begin() ].fr + a[*st.begin()].sc, *st.begin() ) );
   st.erase(st.begin());
  }
  else 
  {
   ans += q2.top().fr;
   st.erase( q2.top().sc );
   q2.pop();
  }
 }
 cout << ans << endl;
}

Compilation message (stderr)

school.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main()
      | ^~~~
school.cpp: In function 'int main()':
school.cpp:29:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   29 |   scanf("%d%d", &a[i].fr, &a[i].sc);
      |          ~^
      |           |
      |           int*
      |          %lld
school.cpp:29:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   29 |   scanf("%d%d", &a[i].fr, &a[i].sc);
      |            ~^
      |             |
      |             int*
      |            %lld
school.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d%d", &a[i].fr, &a[i].sc);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100