oj.uz

Submission #446077

# Submission time Handle Problem Language Result Execution time Memory
446077 2021-07-20T18:00:02 Z ak2006 Schools (IZhO13_school) C++14
95 / 100
 259 ms 22424 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 + 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 0 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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 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 804 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 3192 KB Output is correct
14 Correct 46 ms 6128 KB Output is correct
15 Correct 108 ms 11564 KB Output is correct
16 Correct 132 ms 15120 KB Output is correct
17 Correct 172 ms 16828 KB Output is correct
18 Correct 199 ms 18408 KB Output is correct
19 Correct 214 ms 19644 KB Output is correct
20 Correct 259 ms 22424 KB Output is correct