oj.uz

Submission #243901

# Submission time Handle Problem Language Result Execution time Memory
243901 2020-07-02T05:44:20 Z abacaba Schools (IZhO13_school) C++14
100 / 100
 242 ms 17028 KB 
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
#define int long long
 
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 15;
int n, x, y;
pii a[N];
int ans;
 
multiset <int> s;
int sum;

int pref[N], suff[N];

inline void solve() {
    sort(a + 1, a + 1 + n, [&](pii a, pii b) {
        return mp(a.f - a.se, a.f) > mp(b.f - b.se, b.f);
    });
    for(int i = 1; i <= x; ++i)
        sum += a[i].f, s.insert(a[i].f);
    pref[x] = sum;
    for(int i = x + 1; i <= n; ++i) {
        sum += a[i].f;
        s.insert(a[i].f);

        sum -= *s.begin();
        s.erase(s.begin());
        pref[i] = sum;
    }
    s.clear(), sum = 0;
    for(int i = n - y + 1; i <= n; ++i)
        sum += a[i].se, s.insert(a[i].se);
    suff[n - y + 1] = sum;
    for(int i = n - y; i; --i) {
        sum += a[i].se;
        s.insert(a[i].se);

        sum -= *s.begin();
        s.erase(s.begin());
        suff[i] = sum;
    }
    for(int i = x; i <= n - y; ++i)
        Max(ans, pref[i] + suff[i + 1]);
}
 
main() {
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    // setin("input.txt");
    cin >> n >> x >> y;
    for(int i = 1; i <= n; ++i)
        cin >> a[i].f >> a[i].se;
    solve();
    cout << ans << endl;
    return 0;
}

Compilation message

school.cpp:106:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 7 ms 768 KB Output is correct
13 Correct 27 ms 3200 KB Output is correct
14 Correct 48 ms 4472 KB Output is correct
15 Correct 75 ms 7288 KB Output is correct
16 Correct 151 ms 13944 KB Output is correct
17 Correct 174 ms 13304 KB Output is correct
18 Correct 196 ms 13688 KB Output is correct
19 Correct 209 ms 14764 KB Output is correct
20 Correct 242 ms 17028 KB Output is correct