oj.uz

Submission #30845

# Submission time Handle Problem Language Result Execution time Memory
30845 2017-07-27T16:02:53 Z Kerim Schools (IZhO13_school) C++14
100 / 100
 316 ms 14104 KB 
#include "bits/stdc++.h"
#define MAXN 300009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
PII arr[MAXN];
ll suf[MAXN];
multiset<int>st;
bool cmp(PII x,PII y){
	return (x.ss-x.ff<y.ss-y.ff);
}
int main(){
	//~ #ifndef ONLINE_JUDGE
    //~ freopen("file.in", "r", stdin);
	//~ #endif	
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&arr[i].ff,&arr[i].ss);
	sort(arr+1,arr+n+1,cmp);	
	ll cur=0;
	for(int i=n;i>n-b;i--)
		st.insert(arr[i].ss),cur+=arr[i].ss;
	suf[n-b+1]=cur;	
	for(int i=n-b;i>a;i--){
		if(*st.begin()<arr[i].ss){
			cur-=*st.begin();cur+=arr[i].ss;
			st.erase(st.begin());
			st.insert(arr[i].ss);
		}suf[i]=cur;
	}st.clear();cur=0;
	for(int i=1;i<=a;i++)
		st.insert(arr[i].ff),cur+=arr[i].ff;
	ll ans=cur+suf[a+1];
	for(int i=a+1;i<=n-b;i++){
		if(*st.begin()<arr[i].ff){
			cur-=*st.begin();cur+=arr[i].ff;
			st.erase(st.begin());
			st.insert(arr[i].ff);
		}
		umax(ans,cur+suf[i+1]);	
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:31:26: 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:33:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&arr[i].ff,&arr[i].ss);
                                      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6712 KB Output is correct
2 Correct 0 ms 6712 KB Output is correct
3 Correct 0 ms 6712 KB Output is correct
4 Correct 0 ms 6712 KB Output is correct
5 Correct 0 ms 6712 KB Output is correct
6 Correct 0 ms 6712 KB Output is correct
7 Correct 0 ms 6844 KB Output is correct
8 Correct 3 ms 6976 KB Output is correct
9 Correct 3 ms 6976 KB Output is correct
10 Correct 0 ms 6976 KB Output is correct
11 Correct 3 ms 6844 KB Output is correct
12 Correct 3 ms 6844 KB Output is correct
13 Correct 29 ms 8164 KB Output is correct
14 Correct 59 ms 7768 KB Output is correct
15 Correct 76 ms 6976 KB Output is correct
16 Correct 226 ms 14104 KB Output is correct
17 Correct 203 ms 11728 KB Output is correct
18 Correct 226 ms 11068 KB Output is correct
19 Correct 259 ms 11464 KB Output is correct
20 Correct 316 ms 12124 KB Output is correct