#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const double EPS = 1e-6;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 2e5 + 5;
int n, k, ans[N];
struct Cake {
int v, c;
bool operator<(const Cake &rhs) const { return c < rhs.c; }
} c[N];
double ansOut = 0;
double v2[N], sumV[N], cnt[N];
int solve(double penalty) {
fw (i, 0, n) v2[i] = c[i].v, v2[i] -= penalty;
fw (i, 0, n) {
sumV[i] = (i ? sumV[i - 1] : 0);
cnt[i] = (i ? cnt[i - 1] : 0);
if (v2[i] > 0) {
sumV[i] += v2[i];
cnt[i]++;
}
}
int mxL = -1, ansL, ansR;
double mx = -infll, ans = -infll;
fw (i, 0, n) {
//l and r must be at least 3 elements apart.
double val = (i ? sumV[i - 1] : 0) + v2[i] - 2 * c[i].c;
if (val + mx > ans) {
ans = val + mx;
ansL = mxL;
ansR = i;
}
if (v2[i] - sumV[i] + 2 * c[i].c > mx) {
mx = v2[i] - sumV[i] + 2 * c[i].c;
mxL = i;
}
}
ansOut = ans;
return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
}
double bs(double l, double r) {
if (l + EPS > r) return l;
double m = (l + r) / 2;
int lol = solve(m);
if (lol > k) return bs(m, r); //Increase penalty to pick less elements
return bs(l, m);
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
fw (i, 0, n) cin >> c[i].v >> c[i].c;
sort(c, c + n); //Minimum sum of depth differences is 2 * (max - min)
//Use Alien's trick: Add a penalty for each piece taken until the number of pieces is exactly K.
double optPenalty = bs(-2e9, 2e9);
solve(optPenalty);
cout << (long long)(ansOut + optPenalty * k);
return 0;
}
Compilation message
cake3.cpp: In function 'long long int solve(double)':
cake3.cpp:54:26: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
~~~~~^~~
cake3.cpp:54:46: warning: 'ansL' may be used uninitialized in this function [-Wmaybe-uninitialized]
return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
372 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
372 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
372 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
