oj.uz

Submission #446075

# Submission time Handle Problem Language Result Execution time Memory
446075 2021-07-20T17:59:12 Z ak2006 Schools (IZhO13_school) C++14
95 / 100
 256 ms 25904 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(vi&f,vi&s)
{
    return f[0] - s[0] > f[1] - s[1];
}
int main()
{
    setIO();
    int n,m,s;
    cin>>n>>m>>s;
    vvi a(n + 1,vi(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 + 1);

    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 = m;i<=n;i++)
        if (n - i >= s)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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 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 744 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 3588 KB Output is correct
14 Correct 47 ms 7000 KB Output is correct
15 Correct 110 ms 13312 KB Output is correct
16 Correct 128 ms 17012 KB Output is correct
17 Correct 165 ms 19388 KB Output is correct
18 Correct 195 ms 21116 KB Output is correct
19 Correct 219 ms 22700 KB Output is correct
20 Correct 256 ms 25904 KB Output is correct