#include <iostream>
#include <queue>
using namespace std;
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define int long long
#define pii pair < int, int >
const int N = 3e5 + 1;
priority_queue < pair < int, pii > > v;
priority_queue < pair < int, pii > > vm;
priority_queue < pair < int, pii >, vector < pair < int, pii > >, greater < pair < int, pii > > > pq;
ll ans;
int u[N], um[N], us[N], ii;
int maxim()
{
int id = vm.top().sc.sc;
int res = vm.top().fr;
if(!vm.size())
{
return -1e11;
}
while(u[id] && vm.size())
{
vm.pop();
id = vm.top().sc.sc;
res = vm.top().fr;
}
ii = id;
return res;
}
int maxs(priority_queue < pair < int, pii > > temp)
{
int id = temp.top().sc.sc;
int res = temp.top().fr;
if(!temp.size())
{
return 1e11;
}
while(u[id] && temp.size())
{
temp.pop();
id = temp.top().sc.sc;
res = temp.top().fr;
}
return res;
}
main()
{
int n, m, s;
cin >> n >> m >> s;
for(int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
v.push( { b, {a, i} } );
vm.push( { a, {b, i} } );
pq.push( { a, {b, i} } );
}
int cnt = n - m - s;
while(m--)
{
int mx = vm.top().fr;
int id = vm.top().sc.sc;
us[id] = vm.top().sc.fr;
vm.pop();
u[id] = 1;
um[id] = mx;
ans += mx;
}
while(s)
{
int mx = v.top().fr;
int id = v.top().sc.sc;
v.pop();
if(um[id])
{
int mxm = maxim();
int tmp = ans + us[id] - um[id] + mxm;
mx = maxs(v);
if(ans + mx < tmp)
{
ans = tmp;
s--;
u[ii] = 1;
um[ii] = mxm;
us[ii] = mx;
if(vm.size())
vm.pop();
}
}
else
{
u[id] = 1;
ans += mx;
s--;
}
}
cout << ans << endl;
}
/*
3 1 1
5 2
4 1
6 4
7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4
4 1 1
6 16
2 14
4 5
15 19
*/
Compilation message
school.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
school.cpp: In function 'int main()':
school.cpp:74:6: warning: unused variable 'cnt' [-Wunused-variable]
int cnt = n - m - s;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
508 KB |
Output is correct |
| 3 |
Correct |
2 ms |
508 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
524 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
1128 KB |
Output isn't correct |
| 8 |
Incorrect |
28 ms |
1264 KB |
Output isn't correct |
| 9 |
Incorrect |
18 ms |
1264 KB |
Output isn't correct |
| 10 |
Incorrect |
10 ms |
1264 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
1264 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
1264 KB |
Output isn't correct |
| 13 |
Incorrect |
794 ms |
4912 KB |
Output isn't correct |
| 14 |
Incorrect |
428 ms |
9832 KB |
Output isn't correct |
| 15 |
Incorrect |
203 ms |
17160 KB |
Output isn't correct |
| 16 |
Execution timed out |
2047 ms |
21828 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2037 ms |
26372 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2055 ms |
29016 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2033 ms |
31236 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2041 ms |
35800 KB |
Time limit exceeded |
