oj.uz

답안 #873874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873874 2023-11-16T02:26:13 Z noiaint 학교 설립 (IZhO13_school) C++17
100 / 100
 86 ms 16044 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m, s;
pair<int, int> a[N];
int f[N], g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m >> s;
    for (int i = 1; i <= n; ++i) 
    	cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1, [&] (pair<int, int> x, pair<int, int> y) {
    	return x.fi - x.se > y.fi - y.se;
    });

    priority_queue<int, vector<int>, greater<int> > q;

    for (int i = 1; i <= n; ++i) {
    	f[i] = f[i - 1] + a[i].fi;
    	q.push(a[i].fi);
    	if ((int) q.size() > m) {
    		f[i] -= q.top();
    		q.pop();
    	}
    }

    while (q.size()) q.pop();

    for (int i = n; i >= 1; --i) {
    	g[i] = g[i + 1] + a[i].se;
    	q.push(a[i].se);
    	if ((int) q.size() > s) {
    		g[i] -= q.top();
    		q.pop();
    	}
    }

    int res = 0;
    for (int i = m; i <= n - s; ++i) res = max(res, f[i] + g[i + 1]);

    cout << res;

    return 0;
}

/*

*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 11 ms 3808 KB Output is correct
14 Correct 22 ms 8928 KB Output is correct
15 Correct 42 ms 10160 KB Output is correct
16 Correct 48 ms 12204 KB Output is correct
17 Correct 64 ms 14396 KB Output is correct
18 Correct 74 ms 14664 KB Output is correct
19 Correct 78 ms 15164 KB Output is correct
20 Correct 86 ms 16044 KB Output is correct