이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, K;
cin >> n >> K;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].second >> a[i].first;
}
sort(a.begin(), a.end());
long long ans = -INF;
function<void(int, int, int, int)> solve = [&](int l, int r, int ql, int qr)
{
if (l > r)
{
return;
}
int mid = (l + r) / 2;
pair<long long, int> maxn(-INF, -1);
long long cur = 0;
priority_queue<int, vector<int>, greater<>> pq;
int i = mid;
for (; i > qr; i--)
{
pq.push(a[i].second);
cur += a[i].second;
}
for (; i >= ql; i--)
{
pq.push(a[i].second);
cur += a[i].second;
while (pq.size() > K)
{
cur -= pq.top();
pq.pop();
}
if (pq.size() == K)
{
maxn = max(maxn, make_pair(cur - 2ll * (a[mid].first - a[i].first), i));
}
}
if (maxn.second == -1)
{
return;
}
ans = max(ans, maxn.first);
solve(l, mid - 1, ql, maxn.second);
solve(mid + 1, r, maxn.second, qr);
};
solve(0, n - 1, 0, n - 1);
cout << ans << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cake3.cpp: In lambda function:
cake3.cpp:37:30: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<void> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | while (pq.size() > K)
| ~~~~~~~~~~^~~
cake3.cpp:42:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<void> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if (pq.size() == K)
| ~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |