oj.uz

Submission #84469

# Submission time Handle Problem Language Result Execution time Memory
84469 2018-11-15T11:13:01 Z hamzqq9 Schools (IZhO13_school) C++14
100 / 100
 378 ms 22660 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2005000000
#define MOD 1000000007
#define N 300005
#define M 1000005
#define LOG 18
#define KOK 4000000
using namespace std;

int n,m,s;
ii a[N];
ll ans;
priority_queue<int> q;
multiset<ii> ma,mb;

int main() {

	//freopen("input.txt","r",stdin);
	
	scanf("%d %d %d",&n,&m,&s);

	for(int i=1;i<=n;i++) {

		scanf("%d %d",&a[i].st,&a[i].nd);

	}

	sort(a+1,a+1+n,[](ii x,ii y) {

		if(x.st==y.st) return x.nd<y.nd;

		return x.st>y.st;

	});

	for(int i=1;i<=m;i++) {

		ans+=a[i].st;

		q.push(a[i].nd-a[i].st);

	}

	for(int i=m+1;i<=n;i++) {

		ma.insert(a[i]);
		mb.insert({a[i].nd,a[i].st});

	}

	while(s--) {

		int val=q.top();
		ii adda=*ma.rbegin();
		ii addb=*mb.rbegin();

		if(val+adda.st>addb.st) {

			ans+=val+adda.st;

			q.pop();

			q.push(adda.nd-adda.st);

			ma.erase(prev(ma.end()));

			mb.erase(mb.find({adda.nd,adda.st}));

		}
		else {

			ans+=addb.st;

			mb.erase(prev(mb.end()));

			ma.erase(ma.find({addb.nd,addb.st}));

		}

	}

	printf("%lld",ans);


}

Compilation message

school.cpp: In function 'int main()':
school.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
school.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].st,&a[i].nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 5 ms 916 KB Output is correct
8 Correct 4 ms 916 KB Output is correct
9 Correct 6 ms 916 KB Output is correct
10 Correct 4 ms 916 KB Output is correct
11 Correct 7 ms 1264 KB Output is correct
12 Correct 7 ms 1336 KB Output is correct
13 Correct 18 ms 1640 KB Output is correct
14 Correct 104 ms 8064 KB Output is correct
15 Correct 244 ms 17188 KB Output is correct
16 Correct 348 ms 17320 KB Output is correct
17 Correct 252 ms 17320 KB Output is correct
18 Correct 266 ms 17320 KB Output is correct
19 Correct 312 ms 18924 KB Output is correct
20 Correct 378 ms 22660 KB Output is correct