# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90782 | YottaByte | Schools (IZhO13_school) | C++14 | 2073 ms | 35720 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
if(m + s == n)
{
while(s--)
{
int mx = v.top().fr, id = v.top().sc.sc;
v.pop();
u[id] = 1;
//cout << id + 1 << endl;
u[id] = 1;
ans += mx;
}
while(cnt)
{
int id = pq.top().sc.sc;
int mn = pq.top().fr;
pq.pop();
if(u[id]) continue;
//puts("Del");
//cout << id + 1 << endl;
cnt--;
u[id] = 1;
ans -= mn;
}
}
else
{
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |