#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =1e5 + 1;
const ll linf = 1e18 + 1;
multiset <pll> a, b;
multiset <pll, greater<pll> > c, d;
ll sum = 0;
ll A[nmax], B[nmax];
void erase1(){
int x = a.begin()->s;
c.erase({B[x] - A[x], x});
a.erase(a.begin());
}
void erase2(){
int x = b.begin()->s;
d.erase({A[x] - B[x], x});
b.erase(b.begin());
}
int main(){
int n; cin >> n;
int m; cin >> m;
int s; cin >> s;
for(int i = 1; i <= n; i++)
cin >> A[i] >> B[i];
ll sum = 0;
vector <pll> vec;
for(int i= 1; i <= s + m; i++){
sum += A[i];
vec.pb({B[i] - A[i], i});
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for(int i = 0; i < s; i++){
int x = vec[i].s;
b.insert({B[x], x});
d.insert({A[x] - B[x], x});
sum += B[x] - A[x];
}
for(int i = s; i < s + m; i++){
int x = vec[i].s;
a.insert({A[x], x});
c.insert({B[x] - A[x], x});
}
for(int i = s + m + 1; i <= n; ++i){
ll val1 = 0;
val1 = sum + A[i];
if(c.empty() || b.empty()) val1= -linf;
else val1 += c.begin()->f - b.begin()->f;
ll val2 = sum + A[i];
if(a.empty()) val2 = -linf;
else val2 -= a.begin()->f;
ll val3 = 0;
val3 = sum + B[i];
if(d.empty() || a.empty()) val3 = -linf;
else val3 += d.begin()->f - a.begin()->f;
ll val4 = sum + B[i];
if(b.empty()) val4= -linf;
else val4 -= b.begin()->f;
ll mx = max({val1, val2, val3, val4, sum});
if(mx == sum) continue;
if(mx == val1){
erase2();
int x = c.begin()->s;
a.erase({A[x], x});
c.erase(c.begin());
b.insert({B[x], x});
d.insert({A[x] - B[x], x});
a.insert({A[i], i});
c.insert({B[i] - A[i], i});
sum = val1;
continue;
}
if(mx == val2){
erase1();
a.insert({A[i], i});
a.insert({B[i] - A[i], i});
sum = val2;
continue;
}
if(mx == val3){
erase1();
int x = d.begin()->s;
b.erase({B[x], x});
d.erase(d.begin());
a.insert({A[x], x});
c.insert({B[x] - A[x], x});
b.insert({B[i], i});
d.insert({A[i] - B[i], i});
sum = val3;
continue;
}
if(mx == val4){
erase2();
b.insert({B[i], i});
d.insert({A[i] - B[i], i});
sum = val3;
continue;
}
}
cout << sum;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
596 KB |
Output isn't correct |
| 8 |
Correct |
5 ms |
980 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
980 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
980 KB |
Output isn't correct |
| 11 |
Incorrect |
7 ms |
852 KB |
Output isn't correct |
| 12 |
Incorrect |
5 ms |
824 KB |
Output isn't correct |
| 13 |
Incorrect |
41 ms |
5576 KB |
Output isn't correct |
| 14 |
Incorrect |
86 ms |
6160 KB |
Output isn't correct |
| 15 |
Runtime error |
52 ms |
3464 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
50 ms |
3452 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
65 ms |
3488 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
50 ms |
3556 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
50 ms |
3596 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
50 ms |
3464 KB |
Execution killed with signal 11 |
