Submission #171685

#	Time	Username	Problem	Language	Result	Execution time	Memory
171685		SamAnd	학교 설립 (IZhO13_school)	C++17	100 / 100	125 ms	7992 KiB

school

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const long long INF = 1000000009000000009;
struct ban
{
    int m, s;
};
bool operator<(const ban& a, const ban& b)
{
    return (a.m - a.s) > (b.m - b.s);
}

int n, m, s;
ban a[N];

long long pp[N], ss[N];

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i].m, &a[i].s);
    sort(a + 1, a + n + 1);
    long long sum = 0;
    priority_queue<int> q;
    if (m == 0)
        pp[0] = 0;
    else
        pp[0] = -INF;
    for (int i = 1; i <= n; ++i)
    {
        if (q.size() < m)
        {
            q.push(-a[i].m);
            sum += a[i].m;
        }
        else
        {
            if (!q.empty() && a[i].m > -q.top())
            {
                sum += q.top();
                q.pop();
                q.push(-a[i].m);
                sum += a[i].m;
            }
        }
        if (q.size() < m)
            pp[i] = -INF;
        else
            pp[i] = sum;
    }
    sum = 0;
    while (!q.empty())
        q.pop();
    if (s == 0)
        ss[n + 1] = 0;
    else
        ss[n + 1] = -INF;
    for (int i = n; i >= 1; --i)
    {
        if (q.size() < s)
        {
            q.push(-a[i].s);
            sum += a[i].s;
        }
        else
        {
            if (!q.empty() && a[i].s > -q.top())
            {
                sum += q.top();
                q.pop();
                q.push(-a[i].s);
                sum += a[i].s;
            }
        }
        if (q.size() < s)
            ss[i] = -INF;
        else
            ss[i] = sum;
    }
    long long ans = -INF;
    for (int i = 0; i <= n; ++i)
    {
        ans = max(ans, pp[i] + ss[i + 1]);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (q.size() < m)
             ~~~~~~~~~^~~
school.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (q.size() < m)
             ~~~~~~~~~^~~
school.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (q.size() < s)
             ~~~~~~~~~^~~
school.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (q.size() < s)
             ~~~~~~~~~^~~
school.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].m, &a[i].s);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100