#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn = 1 << 18;
const ll inf = 1e18;
int cnt[maxn * 2];
ll sum[maxn * 2];
void update(int val, int vr)
{
vr += maxn, cnt[vr] = (val ? 1 : 0), sum[vr] = val;
for (vr = vr >> 1; vr > 0; vr >>= 1) cnt[vr] = cnt[vr << 1] + cnt[vr << 1 | 1], sum[vr] = sum[vr << 1] + sum[vr << 1 | 1];
}
int n, m, L = 0, R = -1;
struct cake { ll v, c; } c[maxn];
bool cmp(const cake& a, const cake& b) { return a.c < b.c; }
pair<ll, int> v2[maxn];
int ord[maxn];
ll mbest()
{
ll val = 0; int left = m;
for (int vr = 1; vr < maxn;)
if (cnt[vr << 1] <= left)
{
left -= cnt[vr << 1];
val += sum[vr << 1];
vr = vr << 1 | 1;
}
else vr = vr << 1;
return val;
}
void fix(int l, int r)
{
while (R < r) R++, update(c[R].v, ord[R]);
while (L > l) L--, update(c[L].v, ord[L]);
while (R > r) update(0, ord[R]), R--;
while (L < l) update(0, ord[L]), L++;
/*ll a = 0;
for (int i = L; i <= R; i++) a += c[i].v;
cout << L << " " << R << " " << sum[1] << " " << a << "\n";*/
}
ll ans = -inf;
void dc(int l1, int l2, int r1, int r2)
{
if (l2 < l1) return;
int mid = (l1 + l2) >> 1;
pair<ll, int> p(-inf, -1);
for (int i = max(mid + m - 1, r1); i <= r2; i++)
{
fix(mid, i);
pair<ll, int> p2(mbest() - 2ll * (c[i].c - c[mid].c), i);
p = max(p, p2);
}
ans = max(ans, p.first);
dc(l1, mid - 1, r1, p.second);
dc(mid + 1, l2, p.second, r2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> c[i].v >> c[i].c, v2[i] = { c[i].v, i };
sort(c, c + n, cmp);
sort(v2, v2 + n, greater<pair<int, int> > ());
for (int i = 0; i < n; i++)
ord[v2[i].second] = i;
dc(0, n - m, m - 1, n - 1);
cout << ans << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
