# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90783 | YottaByte | Schools (IZhO13_school) | C++14 | 136 ms | 9256 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 mk make_pair
#define fr first
#define sc second
using namespace std;
const int N = 3e5 + 5;
int n, x, y, cn1, cn2, used[N];
pair <int, int> a[N];
vector < pair <int, int> > vec1, vec2;
vector <int> ind;
long long ans;
main()
{
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].fr, &a[i].sc);
vec1.pb( {a[i].fr, i} );
vec2.pb( {a[i].sc, i} );
}
sort( vec1.rbegin(), vec1.rend() );
sort( vec2.rbegin(), vec2.rend() );
for (int i = 0; i < x; i++)
used[ vec1[i].second ]++, ans += vec1[i].fr;
for (int i = 0; i < y; i++){
used[ vec2[i].second ]++, ans += vec2[i].fr;
if ( used[ vec2[i].sc ] == 2 )
ind.pb( vec2[i].sc );
}
while ( cn1 < vec1.size() && used[ vec1[cn1].sc ] )
cn1++;
while ( cn2 < vec2.size() && used[ vec2[cn2].sc ] )
cn2++;
for (auto to : ind)
{
if ( cn2 == vec2.size() || a[to].fr - a[ vec1[cn1].sc ].fr < a[to].sc - a[ vec2[cn2].sc ].sc )
{
ans -= a[to].fr;
ans += a[ vec1[cn1].sc ].fr;
used[ vec1[cn1].sc ]++;
used[ to ]--;
while ( cn1 < vec1.size() && used[ vec1[cn1].sc ] )
cn1++;
}
else
{
ans -= a[to].sc;
ans += a[ vec2[cn2].sc ].sc;
used[ vec2[cn2].sc ]++;
used[ to ]--;
while ( cn2 < vec2.size() && used[ vec2[cn2].sc ] )
cn2++;
}
}
cout << ans << endl;
}
/**
7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4
**/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |