This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;
/*
its always optimal to arrange your chosen cake slices monotonically
n <= 2000:
- sort all slices by increasing colour
- for each L, answer the best value u can get for all R
- iterate through R with a priority queue of cake values
- replace cake whenever u reach a better one
- n^2 log n
*/
ll n, m;
vt<pl> cakes;
main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
cakes.resize(n); F0R (i, n) cin >> cakes[i].s >> cakes[i].f;
sort(all(cakes)); // colour, value
ll best = -INF;
F0R (l, n) {
ll tot = cakes[l].s;
priority_queue<ll, vt<ll>, greater<ll>> pq;
FOR (r, l + 1, n) {
tot += cakes[r].s;
if (pq.size() + 2 > m) {
tot -= pq.top();
pq.pop();
}
pq.push({cakes[r].s});
if (pq.size() + 1 == m) {
best = max(best, tot - 2 * (cakes[r].f - cakes[l].f));
}
}
}
cout << best << endl;
}
Compilation message (stderr)
cake3.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
35 | main() {
| ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:48:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
48 | if (pq.size() + 2 > m) {
| ~~~~~~~~~~~~~~^~~
cake3.cpp:53:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
53 | if (pq.size() + 1 == m) {
| ~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |