oj.uz

답안 #84475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84475 2018-11-15T11:23:00 Z hamzqq9 학교 설립 (IZhO13_school) C++14
100 / 100
 189 ms 11704 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;
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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 4 ms 692 KB Output is correct
8 Correct 4 ms 712 KB Output is correct
9 Correct 4 ms 740 KB Output is correct
10 Correct 4 ms 920 KB Output is correct
11 Correct 4 ms 920 KB Output is correct
12 Correct 4 ms 1092 KB Output is correct
13 Correct 22 ms 2500 KB Output is correct
14 Correct 41 ms 4476 KB Output is correct
15 Correct 76 ms 7260 KB Output is correct
16 Correct 97 ms 8572 KB Output is correct
17 Correct 126 ms 9472 KB Output is correct
18 Correct 140 ms 9988 KB Output is correct
19 Correct 189 ms 10496 KB Output is correct
20 Correct 169 ms 11704 KB Output is correct