oj.uz

Submission #446078

# Submission time Handle Problem Language Result Execution time Memory
446078 2021-07-20T18:06:51 Z ak2006 Schools (IZhO13_school) C++14
100 / 100
 255 ms 22428 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
bool cmp(vl&f,vl&s)
{
    return f[0] - s[0] > f[1] - s[1];
}
int main()
{
    setIO();
    int n,m,s;
    cin>>n>>m>>s;
    vvl a(n + 1,vl(2));
    for (int i = 1;i<=n;i++)cin>>a[i][0]>>a[i][1];
    sort(a.begin() + 1,a.end(),cmp);
    
    vl pref(n + 1),suf(n + 2);

    priority_queue<ll>q;
    ll sum = 0;
    for (int i = 1;i<=n;i++){
        q.push(-a[i][0]);
        sum += a[i][0];
        if (q.size() > m){
            ll val = -q.top();
            q.pop();
            sum -= val;
        }
        pref[i] = sum;
    }
    
    while (!q.empty())q.pop();

    sum = 0;

    for (int i = n;i>=1;i--){
        q.push(-a[i][1]);
        sum += a[i][1];
        if (q.size() > s){
            ll val = -q.top();
            q.pop();
            sum -= val;
        }
        suf[i] = sum;
    }

    ll ans = 0;

    for (int i = 0;i<=n;i++)ans = max(ans,pref[i] + suf[i + 1]);

    cout<<ans;
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:40:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         if (q.size() > m){
      |             ~~~~~~~~~^~~
school.cpp:55:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         if (q.size() > s){
      |             ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 3 ms 716 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 23 ms 3148 KB Output is correct
14 Correct 46 ms 6120 KB Output is correct
15 Correct 103 ms 11564 KB Output is correct
16 Correct 126 ms 15112 KB Output is correct
17 Correct 168 ms 16832 KB Output is correct
18 Correct 190 ms 18344 KB Output is correct
19 Correct 225 ms 19644 KB Output is correct
20 Correct 255 ms 22428 KB Output is correct