# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
725294 | fdnfksd | Schools (IZhO13_school) | C++14 | 84 ms | 13760 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 <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1e16+7;
using namespace std;
const ll N = 2e5;
ll tong, m, n, k, ans=mod, p, t, b[N], c[N], a[N], rb[N], ra[N], lab[N];
pll d[N*3];
//bool check;
string s;
vector<ll> kq, pre;
priority_queue< ll > pb, pa;
void sol()
{
cin >> k >> n >> m;
p=k-n-m;
for(int i = 1 ; i <= k ;i ++)
{
cin >> a[i] >> b[i] ;
a[i]*=-1;
b[i]*=-1;
c[i]=0;
d[i].se = i;
d[i].fi = a[i] - b[i];
tong += c[i];
}
sort(d+1, d+1+k,greater<pair<int,int>>());
// cout <<'\n';
// for(int i=1;i<=k;i++) cout << d[i].se<<' '<<a[d[i].se]-c[d[i].se]<<' '<<b[d[i].se]-c[d[i].se]<<'\n';
// cout << '\n';
for(int i = 1; i <= k; i ++)
{
pb.push(b[d[i].se] - c[d[i].se]);
rb[i] = rb[i-1] + b[d[i].se] - c[d[i].se];
while(pb.size() > m)
{
rb[i] -= pb.top();
pb.pop();
}
}
for(int i = k; i > 0; i --)
{
pa.push(a[d[i].se] - c[d[i].se]);
ra[i] = ra[i+1] + a[d[i].se] - c[d[i].se];
while(pa.size() > n)
{
ra[i] -= pa.top();
pa.pop();
}
}
for(int i = m; i <= k - n; i ++)
{
//if(i==k-n) cout << ra[i+1]<<' '<<rb[i]<<'\n';
ans = min(ans, tong + ra[i+1] + rb[i]);
}
cout << -ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ntest;
ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |