#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(){
freopen("school.in", "r", stdin);
freopen("school.out", "w", stdout);
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 = val4;
continue;
}
}
cout << sum;
return 0;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen("school.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen("school.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 13 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 15 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 19 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
