Submission #676593

#	Time	Username	Problem	Language	Result	Execution time	Memory
676593		QwertyPi	Schools (IZhO13_school)	C++14	100 / 100	215 ms	17644 KiB

school

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct area{
	int a, b;
};

int32_t main(){
	int N, M, S;
	cin >> N >> M >> S;
	vector<area> A;
	for(int i = 0; i < N; i++){
		int a, b; cin >> a >> b;
		A.push_back({a, b});
	}
	sort(A.begin(), A.end(), [](area x, area y){
		return x.a > y.a;
	});
	
	int ans = 0;
	for(int i = 0; i < M; i++){
		ans += A[i].a;
	}
	
	priority_queue<pair<int, int>> pq, pqe, pq1, pq1e, pq2, pq2e;
	for(int i = M; i < N; i++){
		pq.push({A[i].a, i});
	}
	for(int i = 0; i < M; i++){
		pq1.push({A[i].b - A[i].a, i});
	}
	for(int i = M; i < N; i++){
		pq2.push({A[i].b, i});
	}
	for(int i = 0; i < S; i++){
		while(pq.size() && pqe.size() && pq.top() < pqe.top()) pqe.pop(); while(pq.size() && pqe.size() && pq.top() == pqe.top()) pq.pop(), pqe.pop();
		while(pq1.size() && pq1e.size() && pq1.top() < pq1e.top()) pq1e.pop(); while(pq1.size() && pq1e.size() && pq1.top() == pq1e.top()) pq1.pop(), pq1e.pop();
		while(pq2.size() && pq2e.size() && pq2.top() < pq2e.top()) pq2e.pop(); while(pq2.size() && pq2e.size() && pq2.top() == pq2e.top()) pq2.pop(), pq2e.pop();
		if(pq1.top().first + pq.top().first > pq2.top().first){
			ans += pq1.top().first + pq.top().first; pq1.pop(); int added = pq.top().second; pq.pop(); pq2e.push({A[added].b, added}); pq1.push({A[added].b - A[added].a, added});
		}else{
			ans += pq2.top().first; int added = pq2.top().second; pqe.push({A[added].a, added}); pq2.pop();
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

school.cpp: In function 'int32_t main()':
school.cpp:37:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   37 |   while(pq.size() && pqe.size() && pq.top() < pqe.top()) pqe.pop(); while(pq.size() && pqe.size() && pq.top() == pqe.top()) pq.pop(), pqe.pop();
      |   ^~~~~
school.cpp:37:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   37 |   while(pq.size() && pqe.size() && pq.top() < pqe.top()) pqe.pop(); while(pq.size() && pqe.size() && pq.top() == pqe.top()) pq.pop(), pqe.pop();
      |                                                                     ^~~~~
school.cpp:38:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   38 |   while(pq1.size() && pq1e.size() && pq1.top() < pq1e.top()) pq1e.pop(); while(pq1.size() && pq1e.size() && pq1.top() == pq1e.top()) pq1.pop(), pq1e.pop();
      |   ^~~~~
school.cpp:38:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   38 |   while(pq1.size() && pq1e.size() && pq1.top() < pq1e.top()) pq1e.pop(); while(pq1.size() && pq1e.size() && pq1.top() == pq1e.top()) pq1.pop(), pq1e.pop();
      |                                                                          ^~~~~
school.cpp:39:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   39 |   while(pq2.size() && pq2e.size() && pq2.top() < pq2e.top()) pq2e.pop(); while(pq2.size() && pq2e.size() && pq2.top() == pq2e.top()) pq2.pop(), pq2e.pop();
      |   ^~~~~
school.cpp:39:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   39 |   while(pq2.size() && pq2e.size() && pq2.top() < pq2e.top()) pq2e.pop(); while(pq2.size() && pq2e.size() && pq2.top() == pq2e.top()) pq2.pop(), pq2e.pop();
      |                                                                          ^~~~~

• Subtask 1: 100 / 100