Submission #342458

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342458	2021-01-02T07:09:48 Z	IZhO_2021_I_want_Silver	Schools (IZhO13_school)	C++14	100 / 100	280 ms	15964 KB

school

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>-

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<" "
#define nl cerr <<"\n"
#define int ll

const int N = 3e5 + 5;

int n, m, s, a[N], b[N], ans, pref[N], suf[N];
vector <pii> vec;
multiset <int> st;

void solve() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        vec.pb({a[i]-b[i], i});
    }
    sort(all(vec));

    int sum = 0;
    if (s > 0) {
        for (int i = 0; i < s; ++i) {
            int ind = vec[i].S;
            st.insert(b[ind]);
            sum += b[ind];
        }
        pref[s-1] = sum;
        for (int i = s; i < sz(vec); ++i) {
            int ind = vec[i].S, mn = *st.begin();
            if (b[ind] > mn) {
                st.erase(st.find(mn));
                st.insert(b[ind]);
                sum -= mn;
                sum += b[ind];
            }
            pref[i] = sum;
        }
        st.clear();
    }

    if (m > 0) {
        sum = 0;
        for (int i = sz(vec)-1; i >= sz(vec)-m; --i) {
            int ind = vec[i].S;
            st.insert(a[ind]);
            sum += a[ind];
        }
        suf[sz(vec)-m] = sum;
        for (int i = sz(vec)-m-1; i >= 0; --i) {
            int ind = vec[i].S, mn = *st.begin();
            if (a[ind] > mn) {
                st.erase(st.find(mn));
                st.insert(a[ind]);
                sum -= mn;
                sum += a[ind];
            }
            suf[i] = sum;
        }
        st.clear();
    }

    for (int i = 0; i < sz(vec); ++i) {
        ans = max({ans, pref[i], suf[i]});
        if (i + 1 < sz(vec)) { ans = max(ans, pref[i]+suf[i+1]); }
        if (i - 1 >= 0) { ans = max(ans, pref[i-1]+suf[i]); }
    }
    cout << ans;
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
*/

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	3 ms	748 KB	Output is correct
9	Correct	3 ms	748 KB	Output is correct
10	Correct	3 ms	748 KB	Output is correct
11	Correct	3 ms	748 KB	Output is correct
12	Correct	3 ms	748 KB	Output is correct
13	Correct	28 ms	3052 KB	Output is correct
14	Correct	40 ms	4200 KB	Output is correct
15	Correct	57 ms	6756 KB	Output is correct
16	Correct	176 ms	13540 KB	Output is correct
17	Correct	206 ms	12388 KB	Output is correct
18	Correct	207 ms	12828 KB	Output is correct
19	Correct	256 ms	13924 KB	Output is correct
20	Correct	280 ms	15964 KB	Output is correct