/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 300005;
int n, m, s, k;
LL ans = 0;
pair<LL, LL> a[N];
multiset<LL> M, S;
vector<pair<LL, LL>> K;
int main()
{
cin >> n >> m >> s;
k = n - m - s;
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &a[i].first, &a[i].second);
sort(a + 1, a + 1 + n, [](pair<LL, LL> a, pair<LL, LL> b) {
return a.first - a.second < b.first - b.second;
});
for (int i = 1; i <= s; i++)
{
ans += a[i].second;
S.insert(a[i].second);
}
for (int i = s + 1; i <= s + k; i++)
K.PB(a[i]);
for (int i = s + k + 1; i <= n; i++)
{
ans += a[i].first;
M.insert(a[i].first);
}
sort(all(K));
for (int i = 0; i < K.size() && i < m; i++)
{
LL x = K[i].first, y = K[i].second;
swap(K[i].first, K[i].second);
LL d1 = -1, d2 = -1;
if (!M.empty())
d1 = x - (*M.begin());
if (!S.empty())
d2 = y - (*S.begin());
if (max(d1, d2) < 0)
continue;
if (d1 >= d2)
{
M.erase(M.begin());
K[i] = MP(0, 0);
//M.insert(x);
ans += d1;
}
}
sort(all(K));
for (int i = 0; i < K.size() && i < s; i++)
{
LL x = K[i].second, y = K[i].first;
LL d2 = -1;
if (!S.empty())
d2 = y - (*S.begin());
if (d2 < 0)
continue;
S.erase(S.begin());
//M.insert(x);
ans += d2;
}
cout << ans << endl;
return 0;
}
/*
3 1 1
0 100
500 500
100 0
*/
Compilation message
school.cpp: In function 'int main()':
school.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < K.size() && i < m; i++)
~~^~~~~~~~~~
school.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < K.size() && i < s; i++)
~~^~~~~~~~~~
school.cpp:80:12: warning: unused variable 'x' [-Wunused-variable]
LL x = K[i].second, y = K[i].first;
^
school.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &a[i].first, &a[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 8 |
Correct |
4 ms |
632 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 11 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 13 |
Incorrect |
25 ms |
2480 KB |
Output isn't correct |
| 14 |
Incorrect |
46 ms |
3700 KB |
Output isn't correct |
| 15 |
Incorrect |
93 ms |
7364 KB |
Output isn't correct |
| 16 |
Correct |
150 ms |
11536 KB |
Output is correct |
| 17 |
Incorrect |
165 ms |
13220 KB |
Output isn't correct |
| 18 |
Incorrect |
172 ms |
13288 KB |
Output isn't correct |
| 19 |
Incorrect |
191 ms |
14700 KB |
Output isn't correct |
| 20 |
Incorrect |
216 ms |
16252 KB |
Output isn't correct |
