#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 7 , mod = 998244353;
long long n , A , B;
long long a[N] , b[N] ;
long long ans ;
int gA , gB ;
priority_queue<pair< long long , int > > q1 , q2 ;
void clear1(){
if(q1.size() > A){
gA = q1.size() -A ;
priority_queue<long long> aux ;
while(q1.size()){
aux.push(-a[q1.top().second]) ;
q1.pop() ;
}
while(gA--){
ans+=aux.top() ;
aux.pop();
}
}
if(q2.size() > B){
gB = q2.size() -B ;
priority_queue<long long> aux ;
while(q2.size()){
aux.push(-b[q2.top().second]) ;
q2.pop() ;
}
while(gB--){
ans+=aux.top() ;
aux.pop();
}
}
}
int main()
{
// freopen("in.in" , "r" , stdin) ;
cin>>n>>A>>B ;
for(int i = 0 ; i < n ; i++){
cin>>a[i] >> b[i] ;
if(a[i]>=b[i]){
q1.push({ b[i] -a[i],i });
}
else {
q2.push({ a[i] - b[i] , i}) ;
}
ans += max(a[i] , b[i] ) ;
}
if(q1.size() > A && q2.size() > B)
{
clear1();
}
while(q1.size()> A && q2.size() < B){
ans+=q1.top().first ;
q2.push({a[q1.top().second] - b[q1.top().second] ,q1.top().second });
q1.pop();
}
if(q1.size() > A){
priority_queue<pair< pair<long long , long long > , int > > aux1 ;
priority_queue< pair<long long , int > > aux2 ;
while(q1.size())
{
aux1.push( { { b[q1.top().second] - a[q1.top().second], b[q1.top().second]} ,q1.top().second });
q1.pop();
}
while(q2.size())
{
aux2.push({-b[q2.top().second] , q2.top().second });
q2.pop();
}
while(aux1.size() > A && aux1.top().first.second>=-aux2.top().first ) {
ans+=aux2.top().first;
ans+=aux1.top().first.first;
aux2.pop();
aux2.push({-aux1.top().first.second ,aux1.top().second });
aux1.pop();
}
for(int i = 0 ; i < A ; i++)
aux1.pop();
while(aux1.size()){
ans-=a[aux1.top().second];
aux1.pop();
}
}
while(q2.size()> B){
ans+=q2.top().first ;
q1.push({b[q2.top().second] - a[q2.top().second] , q2.top().second}) ;
q2.pop();
}
if(q2.size() > B){
priority_queue<pair< pair<long long , long long > , int > > aux1 ;
priority_queue< pair<long long , int > > aux2 ;
while(q2.size())
{
aux1.push( { { a[q2.top().second] - b[q2.top().second], a[q2.top().second]} ,q2.top().second });
q2.pop();
}
while(q1.size())
{
aux2.push({-a[q1.top().second] , q1.top().second });
q1.pop();
}
while(aux1.size() > B && aux1.top().first.second>=-aux2.top().first ) {
ans+=aux2.top().first;
ans+=aux1.top().first.first;
aux2.pop();
aux2.push({-aux1.top().first.second ,aux1.top().second });
aux1.pop();
}
for(int i = 0 ; i < B ; i++)
aux1.pop();
while(aux1.size()){
ans-=b[aux1.top().second];
aux1.pop();
}
}
clear1();
cout<<ans;
return 0 ;
}
Compilation message
school.cpp: In function 'void clear1()':
school.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q1.size() > A){
~~~~~~~~~~^~~
school.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q2.size() > B){
~~~~~~~~~~^~~
school.cpp: In function 'int main()':
school.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q1.size() > A && q2.size() > B)
~~~~~~~~~~^~~
school.cpp:56:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q1.size() > A && q2.size() > B)
~~~~~~~~~~^~~
school.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(q1.size()> A && q2.size() < B){
~~~~~~~~~^~~
school.cpp:61:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(q1.size()> A && q2.size() < B){
~~~~~~~~~~^~~
school.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q1.size() > A){
~~~~~~~~~~^~~
school.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(aux1.size() > A && aux1.top().first.second>=-aux2.top().first ) {
~~~~~~~~~~~~^~~
school.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(q2.size()> B){
~~~~~~~~~^~~
school.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(q2.size() > B){
~~~~~~~~~~^~~
school.cpp:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(aux1.size() > B && aux1.top().first.second>=-aux2.top().first ) {
~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 8 |
Correct |
9 ms |
632 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
632 KB |
Output isn't correct |
| 10 |
Incorrect |
9 ms |
632 KB |
Output isn't correct |
| 11 |
Incorrect |
9 ms |
760 KB |
Output isn't correct |
| 12 |
Incorrect |
11 ms |
632 KB |
Output isn't correct |
| 13 |
Incorrect |
43 ms |
2536 KB |
Output isn't correct |
| 14 |
Incorrect |
88 ms |
3592 KB |
Output isn't correct |
| 15 |
Incorrect |
184 ms |
7012 KB |
Output isn't correct |
| 16 |
Correct |
174 ms |
8792 KB |
Output is correct |
| 17 |
Incorrect |
243 ms |
9176 KB |
Output isn't correct |
| 18 |
Incorrect |
278 ms |
9880 KB |
Output isn't correct |
| 19 |
Incorrect |
299 ms |
10644 KB |
Output isn't correct |
| 20 |
Incorrect |
347 ms |
12920 KB |
Output isn't correct |
