oj.uz

Submission #90533

# Submission time Handle Problem Language Result Execution time Memory
90533 2018-12-22T09:15:03 Z popovicirobert Schools (IZhO13_school) C++14
0 / 100
 2000 ms 34312 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;

pair <int, int> arr[MAXN + 1];

bool cmp(pair <int, int> a, pair <int, int> b) {
    /*if(a.first - a.second == b.first - b.second) {
        return a.second < b.second;
    }*/
    return a.first - a.second > b.first - b.second;
}

ll pref[MAXN + 1], suff[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, s;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    for(i = 1; i <= n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr + 1, arr + n + 1, cmp);
    for(i = 1; i <= n; i++) {
        cerr << arr[i].first << " " << arr[i].second << "\n";
    }
    multiset <int> mst;
    ll cur = 0;
    for(i = 1; i <= n; i++) {
        if(mst.size() < m) {
            mst.insert(arr[i].first);
            cur += arr[i].first;
        }
        else if(*mst.begin() < arr[i].first) {
            cur -= *mst.begin();
            mst.erase(mst.begin());
            mst.insert(arr[i].first);
            cur += arr[i].first;
        }
        pref[i] = cur;
    }
    mst.clear();
    cur = 0;
    for(i = n; i >= 1; i--) {
        if(mst.size() < s) {
            mst.insert(arr[i].second);
            cur += arr[i].second;
        }
        else if(*mst.begin() < arr[i].second) {
            cur -= *mst.begin();
            mst.erase(mst.begin());
            mst.insert(arr[i].second);
            cur += arr[i].second;
        }
        suff[i] = cur;
    }
    ll ans = 0;
    for(i = m; i <= n - s; i++) {
        ans = max(ans, pref[i] + suff[i + 1]);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mst.size() < m) {
            ~~~~~~~~~~~^~~
school.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mst.size() < s) {
            ~~~~~~~~~~~^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Execution timed out 2045 ms 600 KB Time limit exceeded
3 Incorrect 2 ms 720 KB Output isn't correct
4 Incorrect 2 ms 720 KB Output isn't correct
5 Incorrect 2 ms 720 KB Output isn't correct
6 Incorrect 4 ms 720 KB Output isn't correct
7 Incorrect 26 ms 944 KB Output isn't correct
8 Incorrect 27 ms 1188 KB Output isn't correct
9 Incorrect 27 ms 1236 KB Output isn't correct
10 Incorrect 28 ms 1380 KB Output isn't correct
11 Incorrect 29 ms 1380 KB Output isn't correct
12 Incorrect 30 ms 1444 KB Output isn't correct
13 Incorrect 210 ms 4264 KB Output isn't correct
14 Incorrect 430 ms 6300 KB Output isn't correct
15 Incorrect 847 ms 10268 KB Output isn't correct
16 Incorrect 1050 ms 19964 KB Output isn't correct
17 Incorrect 1293 ms 21536 KB Output isn't correct
18 Incorrect 1386 ms 24640 KB Output isn't correct
19 Incorrect 1496 ms 28736 KB Output isn't correct
20 Incorrect 1769 ms 34312 KB Output isn't correct