Submission #1276799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276799		duckindog	Cake 3 (JOI19_cake3)	C++20	24 / 100	4091 ms	2408 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m;
pair<int, int> p[N];

const long long MAX = 1'000'000'000'000'000;

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> p[i].first >> p[i].second;

    sort(p + 1, p + n + 1, [](const auto& a, const auto& b) { 
        return make_pair(a.second, a.first) < make_pair(b.second, b.first);
    });

    long long answer = -MAX;
    for (int i = 1; i <= n; ++i) { 
        priority_queue<int, vector<int>, greater<>> q;
        long long sum = 0;
        for (int j = i + 1; j <= n; ++j) { 
            if ((int)q.size() == m - 2) { 
                answer = max(answer, p[i].first + 2ll * p[i].second + sum + p[j].first - 2ll * p[j].second);
            }

            sum += p[j].first;
            q.push(p[j].first);
            while ((int)q.size() > m - 2) { 
                sum -= q.top(); q.pop();
            }
        }
    }
    cout << answer << "\n";
}

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