oj.uz

Submission #524090

# Submission time Handle Problem Language Result Execution time Memory
524090 2022-02-08T15:38:30 Z vishesh312 Schools (IZhO13_school) C++17
100 / 100
 106 ms 15100 KB 
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
#define int ll
const int mod = 1e9+7;

void solve(int tc) {
    int n, m, s;
    cin >> n >> m >> s;
    vector<pair<int, int>> v(n);
    for (auto &[a, b]: v)
        cin >> a >> b;
    sort(all(v), [] (pair<int, int> a, pair<int, int> b) {
            return (a.first - a.second) > (b.first - b.second);
    });
    priority_queue<int, vector<int>, greater<>> pq;
    vector<int> asum(n), bsum(n);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        asum[i] = v[i].first + (i ? asum[i-1] : 0);
        pq.push(v[i].first);
        ++cur;
        while (cur > m) {
            asum[i] -= pq.top();
            pq.pop();
            --cur;
        }
    }
    int ans = asum[n-1];
    cur = 0;
    pq = priority_queue<int, vector<int>, greater<>>();
    for (int i = n-1; i >= 0; --i) {
        bsum[i] = v[i].second + (i < n-1 ? bsum[i+1] : 0);
        pq.push(v[i].second);
        ++cur;
        while (cur > s) {
            bsum[i] -= pq.top();
            pq.pop();
            --cur;
        }
        ans = max(ans, (i ? asum[i-1] : 0) + bsum[i]);
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 12 ms 2144 KB Output is correct
14 Correct 28 ms 4092 KB Output is correct
15 Correct 55 ms 7104 KB Output is correct
16 Correct 69 ms 10100 KB Output is correct
17 Correct 78 ms 11500 KB Output is correct
18 Correct 84 ms 12264 KB Output is correct
19 Correct 91 ms 13236 KB Output is correct
20 Correct 106 ms 15100 KB Output is correct