# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
128797 | Plurm | Cake 3 (JOI19_cake3) | C++11 | 2 ms | 256 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int v,c;
vector<pair<int,int> > pieces;
for(int i = 0; i < n; i++){
scanf("%d%d",&v,&c);
pieces.emplace_back(v,c);
}
sort(pieces.begin(), pieces.end(), [](pair<int,int> x, pair<int,int> y){
return x.second < y.second;
});
set<pair<int,int> > s;
long long ans = 0ll;
long long cur = 0ll;
for(int i = 0; i < m; i++){
s.insert(pieces[i]);
cur += 1ll * pieces[i].first;
}
cur -= 2ll * pieces[m-1].second;
cur += 2ll * pieces[0].second;
int l = 0;
int r = m-1;
for(int i = m; i < n; i++){
// Case 1: Remove min
long long test1 = cur;
test1 -= 1ll * s.begin()->first;
test1 += 1ll * pieces[i].first;
test1 += 2ll * pieces[r].second;
test1 -= 2ll * pieces[i].second;
// Case 2: Remove left
long long test2 = cur;
int newl = l;
s.erase(pieces[l]);
while(!s.count(pieces[newl])) newl++;
s.insert(pieces[l]);
test2 -= 1ll * pieces[l].first;
test2 += 1ll * pieces[i].first;
test2 += 2ll * pieces[r].second;
test2 -= 2ll * pieces[i].second;
test2 -= 2ll * pieces[l].second;
test2 += 2ll * pieces[newl].second;
// Case 3: Do nothing
long long test3 = cur;
long long best = max(max(test1, test2), test3);
if(test2 == best){
s.erase(pieces[l]);
s.insert(pieces[i]);
while(!s.count(pieces[l])) l++;
l = newl;
r = i;
}else if(test1 == best){
s.erase(s.begin());
s.insert(pieces[i]);
r = i;
}
cur = best;
ans = max(ans, cur);
}
printf("%lld\n",ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |