Submission #524356

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524356	2022-02-09T05:54:04 Z	ezdp	Schools (IZhO13_school)	C++14	100 / 100	229 ms	13252 KB

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);
	ll n, m, s; cin >> n >> m >> s;
	vector<tuple<ll, ll, ll>> A(n);
	vector<ll> pref(n), suff(n);
	for(auto &[diff, x, y] : A){
		cin >> x >> y;
		diff = y - x;
	}
	sort(all(A));
	priority_queue<ll> pq;
	for(ll i = 0, sum = 0; i < n; i ++){
		ll x = get<1>(A[i]);
		ll 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(ll i = n - 1, sum = 0; i >= 0; i --){
		ll x = get<1>(A[i]);
		ll y = get<2>(A[i]);
		sum += y;
		pq.push(-y);
		if(n - i > s){
			sum += pq.top();
			pq.pop();
		}
		suff[i] = sum;
	}
	ll 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

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:6: warning: unused variable 'y' [-Wunused-variable]
   46 |   ll y = get<2>(A[i]);
      |      ^
school.cpp:57:6: warning: unused variable 'x' [-Wunused-variable]
   57 |   ll x = get<1>(A[i]);
      |      ^

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	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	3 ms	460 KB	Output is correct
8	Correct	3 ms	588 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	4 ms	532 KB	Output is correct
11	Correct	3 ms	588 KB	Output is correct
12	Correct	3 ms	588 KB	Output is correct
13	Correct	34 ms	2124 KB	Output is correct
14	Correct	53 ms	3724 KB	Output is correct
15	Correct	98 ms	6724 KB	Output is correct
16	Correct	122 ms	9528 KB	Output is correct
17	Correct	168 ms	10112 KB	Output is correct
18	Correct	176 ms	10964 KB	Output is correct
19	Correct	187 ms	11704 KB	Output is correct
20	Correct	229 ms	13252 KB	Output is correct