oj.uz

Submission #171685

# Submission time Handle Problem Language Result Execution time Memory
171685 2019-12-30T03:45:52 Z SamAnd Schools (IZhO13_school) C++17
100 / 100
 125 ms 7992 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 4 ms 508 KB Output is correct
13 Correct 19 ms 1400 KB Output is correct
14 Correct 33 ms 2372 KB Output is correct
15 Correct 58 ms 4060 KB Output is correct
16 Correct 76 ms 5360 KB Output is correct
17 Correct 95 ms 5996 KB Output is correct
18 Correct 103 ms 6456 KB Output is correct
19 Correct 112 ms 7004 KB Output is correct
20 Correct 125 ms 7992 KB Output is correct