Submission #921968

#	Time	Username	Problem	Language	Result	Execution time	Memory
921968		boris_mihov	Cake 3 (JOI19_cake3)	C++17	24 / 100	4022 ms	4476 KiB

cake3

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;

int n, k;
int v[MAXN];
int c[MAXN];
int opt[MAXN];
std::pair <int,int> toSort[MAXN];
std::priority_queue <int> pq;

void solve()
{
    std::sort(toSort + 1, toSort + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        c[i] = toSort[i].first;
        v[i] = toSort[i].second;
    }

    k -= 2;
    llong ans = -INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        llong sum = 0;
        llong currAns = -INF;
        while (pq.size()) pq.pop();
        opt[i] = n + 1;

        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (pq.size() == k)
            {
                llong curr = sum + v[i] + v[j] - 2 * (c[j] - c[i]);
                if (currAns < curr)
                {
                    currAns = curr;
                    opt[i] = j;
                }
            }

            sum += v[j];
            pq.push(-v[j]);
            if (pq.size() > k)
            {   
                sum += pq.top();
                pq.pop();
            }
        }
    
        ans = std::max(ans, currAns);
    }

    for (int i = 1 ; i < n ; ++i)
    {
        assert(opt[i] <= opt[i + 1]);
    }

    std::cout << ans << '\n';
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> toSort[i].second >> toSort[i].first;
    }
}   

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void solve()':
cake3.cpp:39:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |             if (pq.size() == k)
      |                 ~~~~~~~~~~^~~~
cake3.cpp:51:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |             if (pq.size() > k)
      |                 ~~~~~~~~~~^~~

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