oj.uz

답안 #160905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160905 2019-10-30T14:01:59 Z mrtsima22 학교 설립 (IZhO13_school) C++17
100 / 100
 151 ms 11508 KB 
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NumberOfOnes __builtin_popcount
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twoll pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define y1 y1922
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
typedef
tree<
  int,// aq pair<int,int> shegidzlia
  null_type,
  less/*_equal*/<int>,// aqac
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
// '_equal' mashin ginda roca multiset gchirdeba
template<class key, class value,class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ordered_map<int, int> my_map;
inline int rin(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
const int maxn = 3e5+10;
ll f1[maxn], f2[maxn];
int main(){FAST;xRand;
//ifstream cin("school.in");
//ofstream cout("school.out");
	two a[maxn];
	int n, A, B;
 
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].f >> a[i].s;
	}
	sort(a+1, a+n+1, [] (two a, two b) -> bool {return a.f - a.s > b.f - b.s;});
 
	priority_queue<int, vector<int>, greater<int> > pq;
 
	ll sum = 0;;
	for(int i = 1; i <= n; i++) {
		sum += a[i].f;
		pq.push(a[i].f);
 
		if(pq.size() > A) {
			sum -= pq.top();
			pq.pop();
		}
		f1[i] = sum;
	}
	while(! pq.empty()) pq.pop(); sum = 0;
 
	for(int i = n; i >= 1; i--) {
		sum += a[i].s;
		pq.push(a[i].s);
 
		if(pq.size() > B) {
			sum -= pq.top();
			pq.pop();
		}
		f2[i] = sum;
	}
 
	ll mx = 0;
	for(int i = A; i <= n-B; i++)
		mx = max(mx, f1[i] + f2[i+1]);
 
	cout << mx << endl;

}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

Compilation message

school.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
school.cpp: In function 'int main()':
school.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pq.size() > A) {
      ~~~~~~~~~~^~~
school.cpp:96:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  while(! pq.empty()) pq.pop(); sum = 0;
  ^~~~~
school.cpp:96:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  while(! pq.empty()) pq.pop(); sum = 0;
                                ^~~
school.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pq.size() > B) {
      ~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 6 ms 2808 KB Output is correct
8 Correct 6 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 6 ms 2808 KB Output is correct
12 Correct 6 ms 2808 KB Output is correct
13 Correct 22 ms 3868 KB Output is correct
14 Correct 42 ms 4984 KB Output is correct
15 Correct 71 ms 6992 KB Output is correct
16 Correct 88 ms 8308 KB Output is correct
17 Correct 112 ms 9176 KB Output is correct
18 Correct 126 ms 9764 KB Output is correct
19 Correct 134 ms 10356 KB Output is correct
20 Correct 151 ms 11508 KB Output is correct