# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
84430 |
2018-11-15T07:39:46 Z |
MrTEK |
Schools (IZhO13_school) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
const int N = 3e5 + 5;
multiset <int> l1,l2,r1,r2;
multiset <int> :: iterator it,it2;
int n,m,s,a[N],b[N],id[N];
ll suml,sumr,ans;
void add_l(int x){
if (l1.size() < m) {
suml += a[x];
l1.insert(-a[x]);
}
else if(m == 0) {
l2.insert(-a[x]);
}
else {
it = l1.end();
it--;
if (-*it < a[x]) {
suml += a[x];
suml -= -*it;
l2.insert(*it);
l1.erase(it);
l1.insert(-a[x]);
}
else
l2.insert(-a[x]);
}
}
void add_r(int x) {
if (r1.size() < s) {
sumr += b[x];
r1.insert(-b[x]);
}
else if (s == 0) {
r2.insert(-b[x]);
}
else {
it = r1.end();
it--;
if (-*it < b[x]) {
sumr += b[x];
sumr -= -*it;
r2.insert(*it);
r1.erase(it);
r1.insert(-b[x]);
}
else
r2.insert(-b[x]);
}
}
void remove_r(int x) {
if (r2.empty()) {
it = r1.find(-b[x]);
if (it != r1.end()) {
sumr -= -*it;
r1.erase(it);
}
}
else {
it = r2.find(-b[x]);
if (it != r2.end()) {
r2.erase(it);
return;
}
it = r1.find(-b[x]);
if (it != r1.end()) {
sumr -= -*it;
r1.erase(it);
if (r2.empty() == false) {
it2 = r2.end();
it2--;
sumr += -*it2;
r1.insert(*it2);
r2.earse(r1);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> s;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i] >> b[i];
id[i] = i;
}
sort(id + 1,id + n + 1,[&](int x,int y) {
if (a[x] - b[x] == a[y] - b[y])
return a[x] >= a[y];
return a[x] - b[x] > a[y] - b[y];
});
for (int i = 1 ; i <= m ; i++)
add_l(id[i]);
for (int i = m + 1 ; i <= n ; i++)
add_r(id[i]);
ans = suml + sumr;
for (int i = m + 1 ; i <= n ; i++) {
if (n - i < s)
break;
add_l(id[i]);
remove_r(id[i]);
ans = max(ans,suml + sumr);
}
cout << ans << "\n";
}
Compilation message
school.cpp: In function 'void add_l(int)':
school.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l1.size() < m) {
~~~~~~~~~~^~~
school.cpp: In function 'void add_r(int)':
school.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r1.size() < s) {
~~~~~~~~~~^~~
school.cpp: In function 'void remove_r(int)':
school.cpp:85:12: error: 'class std::multiset<int>' has no member named 'earse'; did you mean 'erase'?
r2.earse(r1);
^~~~~
erase