Submission #676593

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
676593	2022-12-31T11:40:58 Z	QwertyPi	Schools (IZhO13_school)	C++14	100 / 100	215 ms	17644 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	296 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	296 KB	Output is correct
7	Correct	3 ms	536 KB	Output is correct
8	Correct	3 ms	596 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	4 ms	724 KB	Output is correct
12	Correct	4 ms	656 KB	Output is correct
13	Correct	22 ms	1984 KB	Output is correct
14	Correct	51 ms	5900 KB	Output is correct
15	Correct	120 ms	11456 KB	Output is correct
16	Correct	181 ms	12632 KB	Output is correct
17	Correct	166 ms	13504 KB	Output is correct
18	Correct	163 ms	14284 KB	Output is correct
19	Correct	187 ms	15208 KB	Output is correct
20	Correct	215 ms	17644 KB	Output is correct