oj.uz

Submission #446142

# Submission time Handle Problem Language Result Execution time Memory
446142 2021-07-21T05:58:36 Z wind_reaper Schools (IZhO13_school) C++17
100 / 100
 157 ms 8192 KB 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************



//***************** GLOBAL VARIABLES *****************



//***************** AUXILIARY STRUCTS *****************



//***************** MAIN BODY *****************

void solve(){
	int N, M, S;
	cin >> N >> M >> S;

	vector<array<int64_t, 2>> A(N);
	for(auto& [x, y] : A)
		cin >> x >> y;

	sort(A.begin(), A.end(), [](array<int64_t, 2> a, array<int64_t, 2> b){
		return a[0] - a[1] < b[0] - b[1];
	});

	priority_queue<int64_t> pq;

	int64_t sum = 0;

	for(int i = 0; i < N; i++){
		pq.push(-A[i][1]);
		sum += A[i][1];

		while(pq.size() > S){
			sum += pq.top();
			pq.pop();
		}

		A[i][1] = sum;
	}

	while(!pq.empty()) pq.pop();
	sum = 0;
	int64_t ans = 0;

	for(int i = N - 1; i >= 0; --i){
		pq.push(-A[i][0]);
		sum += A[i][0];

		while(pq.size() > M){
			sum += pq.top();
			pq.pop();
		}

		ans = max(ans, sum + (i ? A[i-1][1] : 0));
	}

	cout << ans << '\n';
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic
*/

Compilation message

school.cpp: In function 'void solve()':
school.cpp:50:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   while(pq.size() > S){
      |         ~~~~~~~~~~^~~
school.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   while(pq.size() > M){
      |         ~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 2 ms 448 KB Output is correct
11 Correct 3 ms 444 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 14 ms 1676 KB Output is correct
14 Correct 38 ms 2792 KB Output is correct
15 Correct 64 ms 4544 KB Output is correct
16 Correct 114 ms 7232 KB Output is correct
17 Correct 103 ms 6924 KB Output is correct
18 Correct 113 ms 7268 KB Output is correct
19 Correct 122 ms 7556 KB Output is correct
20 Correct 157 ms 8192 KB Output is correct