제출 #224760

#제출 시각아이디문제언어결과실행 시간메모리
224760NightlightFeast (NOI19_feast)C++14
100 / 100
251 ms15036 KiB
#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) 메시지

feast.cpp: In function 'int main()':
feast.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &K);
   ~~~~~^~~~~~~~~~~~~~~~~
feast.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &tmp);
     ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...