Submission #84475

#	Time	Username	Problem	Language	Result	Execution time	Memory
84475		hamzqq9	Schools (IZhO13_school)	C++14	100 / 100	189 ms	11704 KiB

school

#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;
int a[N],b[N],plc[N];
ll pre[N],suf[N];
ll ans;
priority_queue<int> q;

void up(int now) {

	if(sz(q)<m) {

		ans+=a[now];

		q.push(-a[now]);

	}
	else {

		int val=q.top();

		if(val+a[now]>0) {

			ans+=val+a[now];

			q.pop();

			q.push(-a[now]);

		}

	}

}

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],&b[i]);

		plc[i]=i;

	}

	sort(plc+1,plc+1+n,[](int x,int y) {

		if(a[x]-b[x]==a[y]-b[y]) return a[x]>a[y];

		return a[x]-b[x]>a[y]-b[y];

	});

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

		up(plc[i]);

		pre[i]=ans;

		swap(a[plc[i]],b[plc[i]]);

	}

	ans=0;

	while(sz(q)) q.pop();

	swap(m,s);

	for(int i=n;i>=1;i--) {

		up(plc[i]);

		suf[i]=ans;

	}

	swap(m,s);

	ans=0;

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

		umax(ans,pre[i]+suf[i+1]);

	} 

	printf("%lld",ans);

}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:63: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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100