| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1299995 | khoavn2008 | Feast (NOI19_feast) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll sum;
int l, r;
bool operator<(const Node& other) const {
return sum < other.sum; // max-heap
}
};
// Kadane nhưng chỉ chạy trong [L..R]
Node get_best(const vector<ll>& a, int L, int R) {
ll cur = 0, best = LLONG_MIN;
int start = L, bestL = L, bestR = L;
for (int i = L; i <= R; i++) {
if (cur + a[i] < a[i]) {
cur = a[i];
start = i;
} else {
cur += a[i];
}
if (cur > best) {
best = cur;
bestL = start;
bestR = i;
}
}
return {best, bestL, bestR};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<ll> a(N+1);
for (int i = 1; i <= N; i++) cin >> a[i];
priority_queue<Node> pq;
// toàn đoạn [1..N]
Node root = get_best(a, 1, N);
if (root.sum > 0) pq.push(root);
ll ans = 0;
while (K-- && !pq.empty()) {
Node cur = pq.top(); pq.pop();
if (cur.sum <= 0) break;
ans += cur.sum;
// tách trái
if (cur.l > 1) {
Node left = get_best(a, cur.l0, cur.l - 1);
if (left.sum > 0) pq.push(left);
}
// tách phải
if (cur.r < N) {
Node right = get_best(a, cur.r + 1, cur.r0);
if (right.sum > 0) pq.push(right);
}
}
cout << ans << "\n";
return 0;
}
