Submission #502026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502026	2022-01-05T06:04:15 Z	Aktan	Schools (IZhO13_school)	C++17	100 / 100	283 ms	25496 KB

school

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17,N=3e5+5;
int pr[N],sf[N];
main(){
    int n,m,k;
    cin >> n >> m >> k;
    vector<int> a(n),b(n);
    vector<pair<pair<int,int>,int>> v;
    for(int i=0;i<n;i++){
    	cin >> a[i] >> b[i];
    	v.push_back({{a[i]-b[i],a[i]},b[i]});
	}
	sort(v.rbegin(),v.rend());
	int sum=0;
	multiset<int> s;
	for(int i=0;i<n;i++){
		sum+=v[i].ft.sc;
		s.insert(v[i].ft.sc);
		if(s.size()>m){
			sum-=*s.begin();
			s.erase(s.begin());
		}
		pr[i]=sum;
	}
	s.clear();
	sum=0;
	for(int i=n-1;i>=0;i--){
		sum+=v[i].sc;
		s.insert(v[i].sc);
		if(s.size()>k){
			sum-=*s.begin();
			s.erase(s.begin());
		}
		sf[i]=sum;
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans=max(ans,pr[i]+sf[i+1]);
	}
	cout << ans;
}

Compilation message

school.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main(){
      | ^~~~
school.cpp: In function 'int main()':
school.cpp:27:14: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |   if(s.size()>m){
      |      ~~~~~~~~^~
school.cpp:38:14: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |   if(s.size()>k){
      |      ~~~~~~~~^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	288 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	300 KB	Output is correct
7	Correct	3 ms	680 KB	Output is correct
8	Correct	4 ms	748 KB	Output is correct
9	Correct	4 ms	688 KB	Output is correct
10	Correct	4 ms	780 KB	Output is correct
11	Correct	4 ms	784 KB	Output is correct
12	Correct	4 ms	784 KB	Output is correct
13	Correct	31 ms	4108 KB	Output is correct
14	Correct	60 ms	6464 KB	Output is correct
15	Correct	107 ms	10992 KB	Output is correct
16	Correct	179 ms	19500 KB	Output is correct
17	Correct	209 ms	19752 KB	Output is correct
18	Correct	221 ms	20520 KB	Output is correct
19	Correct	249 ms	22440 KB	Output is correct
20	Correct	283 ms	25496 KB	Output is correct