oj.uz

답안 #524355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524355 2022-02-09T05:53:09 Z ezdp 학교 설립 (IZhO13_school) C++14
70 / 100
 214 ms 10220 KB 
#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

# 결과 실행 시간 메모리 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