제출 #336457

#제출 시각아이디문제언어결과실행 시간메모리
336457ncduy0303Feast (NOI19_feast)C++17
100 / 100
105 ms11140 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define ll long long const int MAX_N = 3e5 + 1; const int MOD = 1e9 + 7; const int INF = 1e9; const ll LINF = 1e18; struct block { int l, r; ll sum; } b[MAX_N]; int num = 0; void solve() { int n, k; cin >> n >> k; vector<int> a(n); for (int &x : a) cin >> x; for (int i = 0; i < n; i++) { b[num] = {num - 1, num + 1, 0}; int j = i; while (j < n && (ll)a[i] * a[j] >= 0) b[num].sum += a[j++]; i = j - 1; if (!(b[num].sum <= 0 && num == 0)) num++; } if (num > 0 && b[num - 1].sum <= 0) num--; if (num == 0) { cout << 0 << "\n"; return; } b[0].l = b[num - 1].r = -1; int cnt = num / 2 + 1; priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq; for (int i = 0; i < num; i++) pq.push({abs(b[i].sum), i}); vector<bool> vis(num); while (cnt > k) { auto [v, i] = pq.top(); pq.pop(); if (vis[i]) continue; vis[i] = true; cnt--; if (b[i].l == -1) { vis[b[i].r] = true; b[b[b[i].r].r].l = -1; } else if (b[i].r == -1) { vis[b[i].l] = true; b[b[b[i].l].l].r = -1; } else { vis[b[i].r] = vis[b[i].l] = true; b[i].sum += b[b[i].l].sum + b[b[i].r].sum; if (b[b[i].l].l != -1) b[b[b[i].l].l].r = i; if (b[b[i].r].r != -1) b[b[b[i].r].r].l = i; b[i].l = b[b[i].l].l; b[i].r = b[b[i].r].r; vis[i] = 0; pq.push({abs(b[i].sum), i}); } } ll ans = 0; for (int i = 0; i < num; i++) { if (vis[i] || b[i].sum <= 0) continue; ans += b[i].sum; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tc = 1; // cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }
#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...