#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
typedef vector<int> vit;
typedef vector<vit> vitt;
typedef vector<lld> vlt;
typedef vector<vlt> vltt;
typedef vector<pi> vpit;
typedef vector<vpit> vpitt;
typedef long double ld;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
if(0<=y&&y<n&&0<=x&&x<m) return true;
return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
pl arr[333333];
lld ans;
priority_queue<pair<lld,int> > q1;
priority_queue<lld> s;
bool tmr(pl a,pl b){
if(a.x!=b.x) return a.x > b.x;
return a.y > b.y;
}
int main(void){
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
for(int e=0;e<n;e++){
lld a,b;
scanf("%lld%lld",&a,&b);
arr[e] = mk(a,b);
}
sort(arr,arr+n,tmr);
for(int e=0;e<a;e++){
ans += arr[e].x;
q1.push(mk(-(arr[e].x-arr[e].y),e));
}
for(int e=a;e<n;e++){
lld tt1 = arr[e].x - arr[e].y;
if(sz(q1)==0) s.push(arr[e].y);
else{
lld tt2 = -q1.top().x;
int wh = q1.top().y;
if(tt2>=tt1) s.push(arr[e].y);
else{
ans += (arr[e].x-arr[wh].x);
s.push(arr[wh].y);
q1.pop();
q1.push(mk(-tt1,e));
}
}
}
for(int e=0;e<b;e++){
lld tt = s.top();
ans += tt;
s.pop();
}
printf("%lld",ans);
return 0;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&a,&b);
~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&a,&b);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 12 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 13 |
Incorrect |
16 ms |
1916 KB |
Output isn't correct |
| 14 |
Incorrect |
44 ms |
3696 KB |
Output isn't correct |
| 15 |
Incorrect |
68 ms |
6764 KB |
Output isn't correct |
| 16 |
Correct |
101 ms |
7660 KB |
Output is correct |
| 17 |
Incorrect |
110 ms |
10728 KB |
Output isn't correct |
| 18 |
Incorrect |
116 ms |
11496 KB |
Output isn't correct |
| 19 |
Incorrect |
128 ms |
12008 KB |
Output isn't correct |
| 20 |
Incorrect |
157 ms |
13032 KB |
Output isn't correct |
