Submission #676391

#	Time	Username	Problem	Language	Result	Execution time	Memory
676391		vjudge1	Schools (IZhO13_school)	C++17	95 / 100	114 ms	9112 KiB

school

#include <bits/stdc++.h>
#define oo 1e18
#define ii pair<int,int>
using namespace std;
int id[1000010],a[1000010],b[1000010],x,y,n;
long long f[1000010],g[1000010];
priority_queue<int,vector<int>,greater<int> >pq;
bool cmp(int i,int j)
{
    return a[i] - b[i] < a[j] - b[j];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("invest.inp","r",stdin);
    //freopen("invest.out","w",stdout);
    cin >> n >> x >> y;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i] >> b[i];
    }
    for (int i = 1;i <= n;i++)
    {
        id[i] = i;
    }
    sort(id + 1,id + n + 1,cmp);
    for (int i = 1;i <= n;i++)
    {
        f[i] = f[i - 1] + b[id[i]];
        pq.push(b[id[i]]);
        if (pq.size() > y)
        {
            f[i] -= pq.top();
            pq.pop();
        }
    }
    while (pq.size() > 0)
    {
        pq.pop();
    }
    for (int i = n;i >= 1;i--)
    {
        g[i] = g[i + 1] + a[id[i]];
        pq.push(a[id[i]]);
        if (pq.size() > x)
        {
            g[i] -= pq.top();
            pq.pop();
        }
    }
    long long res = 0;
    for (int i = 1;i <= n;i++)
    {
        if ((i >= y) && (n - i >= x))
        {
            res = max(res,f[i] + g[i + 1]);
        }
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if (pq.size() > y)
      |             ~~~~~~~~~~^~~
school.cpp:46:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if (pq.size() > x)
      |             ~~~~~~~~~~^~~

• Subtask 1: 95 / 100