Submission #972044

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972044	2024-04-29T20:11:54 Z	sofija6	Schools (IZhO13_school)	C++14	100 / 100	107 ms	21816 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	2 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	2 ms	6748 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct
9	Correct	3 ms	6748 KB	Output is correct
10	Correct	3 ms	6748 KB	Output is correct
11	Correct	2 ms	6748 KB	Output is correct
12	Correct	2 ms	6748 KB	Output is correct
13	Correct	13 ms	10200 KB	Output is correct
14	Correct	25 ms	11152 KB	Output is correct
15	Correct	45 ms	14024 KB	Output is correct
16	Correct	60 ms	15056 KB	Output is correct
17	Correct	84 ms	17352 KB	Output is correct
18	Correct	88 ms	17856 KB	Output is correct
19	Correct	97 ms	18212 KB	Output is correct
20	Correct	107 ms	21816 KB	Output is correct