| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 208322 | mohamedsobhi777 | 학교 설립 (IZhO13_school) | C++14 | 346 ms | 13060 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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();
}
}
clear1();
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<long long , int > > aux1, aux2 ;
while(q2.size())
{
aux1.push( { 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 && aux2.size() < A && aux1.top().first>=-aux2.top().first ) {
ans+=aux2.top().first;
ans+=aux2.top().first;
aux2.pop();
aux2.push({-aux1.top().first ,aux1.top().second });
aux1.pop();
}
for(int i = 0 ; i < B ; i++)
aux1.pop();
while(aux1.size()){
ans-=b[aux1.top().second];
aux1.pop();
}
}*/
cout<<ans;
return 0 ;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||