Submission #524355

#	Time	Username	Problem	Language	Result	Execution time	Memory
524355		ezdp	Schools (IZhO13_school)	C++14	70 / 100	214 ms	10220 KiB

school

#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define lsb(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are less than x
/// insert(x)		 -> inserts x into the set



int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	/// freopen("filename.in" , "r", stdin); 
	/// freopen("filename.out", "w", stdout);
	int n, m, s; cin >> n >> m >> s;
	vector<tuple<int, int, int>> A(n);
	vector<int> pref(n), suff(n);
	for(auto &[diff, x, y] : A){
		cin >> x >> y;
		diff = y - x;
	}
	sort(all(A));
	priority_queue<int> pq;
	for(int i = 0, sum = 0; i < n; i ++){
		int x = get<1>(A[i]);
		int y = get<2>(A[i]);
		sum += x;
		pq.push(-x);
		if((i + 1) > m){
			sum += pq.top();
			pq.pop();
		}
		pref[i] = sum;
	}
	while(!pq.empty()) pq.pop();
	for(int i = n - 1, sum = 0; i >= 0; i --){
		int x = get<1>(A[i]);
		int y = get<2>(A[i]);
		sum += y;
		pq.push(-y);
		if(n - i > s){
			sum += pq.top();
			pq.pop();
		}
		suff[i] = sum;
	}
	int ans = 0;
	for(int i = m - 1; i + s < n; i ++){
		ans = max(ans, pref[i] + suff[i + 1]);
	}
	cout << ans << endl;
}
/**
3 1 1
5 2
4 1
6 4
9

7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4
38
*/

Compilation message (stderr)

school.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
school.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
school.cpp: In function 'int main()':
school.cpp:38:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto &[diff, x, y] : A){
      |            ^
school.cpp:46:7: warning: unused variable 'y' [-Wunused-variable]
   46 |   int y = get<2>(A[i]);
      |       ^
school.cpp:57:7: warning: unused variable 'x' [-Wunused-variable]
   57 |   int x = get<1>(A[i]);
      |       ^

• Subtask 1: 70 / 100