Submission #573992

#	Time	Username	Problem	Language	Result	Execution time	Memory
573992		YouAreMyGalaxy	Cake 3 (JOI19_cake3)	C++17	24 / 100	4083 ms	6628 KiB

cake3

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 2e5;
int id[N + 1], a[N + 1], b[N + 1];
int n, m;
long long res = -1e18;
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i] >> b[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, [&](const int &x, const int &y)
         {
             return b[x] < b[y];
         });
}
void solve()
{
    for (int i = 1; i <= n; ++ i)
    {
        priority_queue<int, vector<int>, greater<int> > PQ;
        long long sum = 0;
        int l = id[i];
        for (int j = i; j <= n; ++ j)
        {
            int r = id[j];
            sum += a[r];
            PQ.push(a[r]);
            if (PQ.size() > m)
            {
                sum -= PQ.top();
                PQ.pop();
            }
            if (PQ.size() == m)
            {
                res = max(res, sum - 2 * (b[r] - b[l]));
            }
        }
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case #" << __ << ":" << '\n';
        read();
        solve();
    }
}

Compilation message (stderr)

cake3.cpp: In function 'void solve()':
cake3.cpp:36:27: 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]
   36 |             if (PQ.size() > m)
      |                 ~~~~~~~~~~^~~
cake3.cpp:41:27: 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]
   41 |             if (PQ.size() == m)
      |                 ~~~~~~~~~~^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76