# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
224760 | Nightlight | Feast (NOI19_feast) | C++14 | 251 ms | 15036 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<long long, int>
#define abval first
#define pos second
#define ABS(n) (n < 0 ? -n : n)
using namespace std;
int N, K, P;
long long A[300005];
int L[300005], R[300005];
long long ans = 0;
set<pii> seto;
int main() {
// freopen("inp", "r", stdin);
scanf("%d %d", &N, &K);
long long tmp;
while(N--) {
scanf("%lld", &tmp);
if(P == 0) {
if(tmp <= 0) continue;
else {
A[++P] = tmp;
}
}else if(!((A[P] > 0) ^ (tmp > 0))) {
A[P] += tmp;
}else {
A[++P] = tmp;
}
}
if(A[P] < 0) {
A[P] = 0;
P--;
}
for(int i = 1; i <= P; i++) {
seto.insert({ABS(A[i]), i});
L[i] = i - 1;
R[i] = i + 1;
}
R[P] = 0;
int cnt = (P >> 1) + 1;
long long l, m, r, tmpval;
while(cnt > K) {
pii now = *seto.begin();
seto.erase(now);
m = now.pos, l = L[m], r = R[m];
tmpval = A[m];
if(A[m] > 0)cnt--;
if(l != 0) {
if(A[l] > 0) cnt--;
seto.erase({ABS(A[l]), l});
tmpval += A[l];
if(L[l] != 0) R[L[l]] = m;
}
if(r != 0) {
if(A[r] > 0) cnt--;
seto.erase({ABS(A[r]), r});
tmpval += A[r];
if(R[r] != 0) L[R[r]] = m;
}
A[m] = tmpval;
A[l] = 0, A[r] = 0;
L[m] = L[l], R[m] = R[r];
if(L[m] == 0 && A[m] < 0) {
L[R[m]] = 0;
A[m] = 0;
}else if(R[m] == 0 && A[m] < 0) {
R[L[m]] = 0;
A[m] = 0;
}else seto.insert({ABS(tmpval), m});
cnt += (A[m] > 0);
// for(int i = 1; i <= P; i++) {
// cout << A[i] << " ";
// }
// cout << "\n";
}
for(auto i : seto) {
ans += A[i.pos] > 0 ? A[i.pos] : 0;
}
printf("%lld\n", ans);
}
컴파일 시 표준 에러 (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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |