이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int n, m;
vector<array<ll, 2>> c; // c, v
pair<ll,ll> solve2(int r, int optl, int optr) {
if (r<m-1) return {-1e18,-1};
// l in [optl, optr]
priority_queue<ll, vector<ll>, greater<ll>> q; // v
ll sum = 0;
for (int i = r; i > r-m; i--) {
q.push(c[i][1]);
sum += c[i][1];
}
pair<ll,ll> ans = {sum - 2 * (c[r][0] - c[r - m + 1][0]), r-m+1};
for (int i = r-m; i >= optl; i--) {
q.push(c[i][1]);
sum += c[i][1];
sum -= q.top();
q.pop();
ans = max(ans, {sum - 2*(c[r][0] - c[i][0]), i});
}
return ans;
}
ll ans = -1e18;
void solve(int l, int r, int optl, int optr) {
int mid = (l + r) / 2;
auto [beauty, opt] = solve2(mid, optl, optr);
ans = max(ans, beauty);
// recurse
solve(l, mid, optl, opt);
solve(mid + 1, r, opt, optr);
}
int main() {
cin >> n >> m;
c.resize(n);
for (int i = 0; i < n; i++) cin >> c[i][1] >> c[i][0];
sort(c.begin(), c.end());
solve(0, n-1, 0, n-1);
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |