Submission #972044

#	Time	Username	Problem	Language	Result	Execution time	Memory
972044		sofija6	Schools (IZhO13_school)	C++14	100 / 100	107 ms	21816 KiB

school

#include <bits/stdc++.h>
#define ll long long
#define MAXN 300010
using namespace std;
ll a[MAXN],b[MAXN],dppref[MAXN],dpsuff[MAXN];
vector<pair<ll,ll> > d;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,s;
    cin >> n >> m >> s;
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i];
        d.push_back({a[i]-b[i],i});
    }
    sort(d.begin(),d.end(),greater<pair<ll,ll> >());
    priority_queue<ll,vector<ll>,greater<ll> > q;
    ll sum=0,cur=0;
    for (auto i : d)
    {
        sum+=a[i.second];
        q.push(a[i.second]);
        while (q.size()>m)
        {
            sum-=q.top();
            q.pop();
        }
        if (q.size()==m)
            dppref[cur]=sum;
        cur++;
    }
    while (!q.empty())
        q.pop();
    reverse(d.begin(),d.end());
    sum=0;
    cur=n-1;
    for (auto i : d)
    {
        sum+=b[i.second];
        q.push(b[i.second]);
        while (q.size()>s)
        {
            sum-=q.top();
            q.pop();
        }
        if (q.size()==s)
            dpsuff[cur]=sum;
        cur--;
    }
    ll ans=0;
    for (ll i=m-1;i<n-s;i++)
        ans=max(ans,dppref[i]+dpsuff[i+1]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:24:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   24 |         while (q.size()>m)
      |                ~~~~~~~~^~
school.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   29 |         if (q.size()==m)
      |             ~~~~~~~~^~~
school.cpp:42:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |         while (q.size()>s)
      |                ~~~~~~~~^~
school.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |         if (q.size()==s)
      |             ~~~~~~~~^~~

• Subtask 1: 100 / 100