Submission #524355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524355	2022-02-09T05:53:09 Z	ezdp	Schools (IZhO13_school)	C++14	70 / 100	214 ms	10220 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);
	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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	288 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	3 ms	332 KB	Output is correct
8	Correct	4 ms	428 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	4 ms	460 KB	Output is correct
11	Correct	4 ms	460 KB	Output is correct
12	Correct	3 ms	460 KB	Output is correct
13	Correct	26 ms	1540 KB	Output is correct
14	Correct	53 ms	2820 KB	Output is correct
15	Correct	101 ms	5172 KB	Output is correct
16	Incorrect	124 ms	6928 KB	Output isn't correct
17	Incorrect	162 ms	7760 KB	Output isn't correct
18	Incorrect	181 ms	8472 KB	Output isn't correct
19	Incorrect	190 ms	8920 KB	Output isn't correct
20	Incorrect	214 ms	10220 KB	Output isn't correct