oj.uz

Submission #377365

# Submission time Handle Problem Language Result Execution time Memory
377365 2021-03-14T06:12:30 Z ijxjdjd Schools (IZhO13_school) C++14
100 / 100
 230 ms 18668 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	int M, S;
	cin >> N >> M >> S;
	vector<pair<ll, ll>> vec(N);
	FR(i, N) {
        cin >> vec[i].first >> vec[i].second;
	}
	sort(all(vec), [](const auto& lhs, const auto& rhs) {
            return lhs.first - lhs.second > rhs.first - rhs.second;
        });
    vector<ll> suf(N);
    vector<ll> pref(N);
    multiset<int> mx;
    ll sm = 0;
    for (int i = N-1; i >= 0; i--) {
        mx.insert(vec[i].second);
        sm += vec[i].second;
        if (mx.size() > S) {
            sm -= *mx.begin();
            mx.erase(mx.begin());
        }
        suf[i] = sm;
    }
    mx.clear();
    sm = 0;
    for (int i = 0; i < N; i++) {
        mx.insert(vec[i].first);
        sm += vec[i].first;
        if (mx.size() > M) {
            sm -= *mx.begin();
            mx.erase(mx.begin());
        }
        pref[i] = sm;
    }
    ll ans = max(suf[0], pref[N-1]);
    for (int i = 0; i + 1 < N; i++) {
        ans = max(pref[i] + suf[i+1], ans);
    }
    cout << ans << '\n';
	return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:29:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         if (mx.size() > S) {
      |             ~~~~~~~~~~^~~
school.cpp:40:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         if (mx.size() > M) {
      |             ~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 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 4 ms 748 KB Output is correct
13 Correct 22 ms 3308 KB Output is correct
14 Correct 40 ms 4716 KB Output is correct
15 Correct 60 ms 7404 KB Output is correct
16 Correct 170 ms 15340 KB Output is correct
17 Correct 167 ms 14828 KB Output is correct
18 Correct 171 ms 15084 KB Output is correct
19 Correct 220 ms 16384 KB Output is correct
20 Correct 230 ms 18668 KB Output is correct