#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, K;
vector <int> A;
pair<int, int> compute(int penalty) {
int total = 0, segments = 0, curr = 0;
for (int i = 0; i < N; ++i) {
curr += A[i];
if (curr - penalty > 0) {
total += curr - penalty;
++segments;
curr = 0;
} else if (curr < 0) {
curr = 0;
}
}
return {total, segments};
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
A.resize(N);
for (int& x : A) cin >> x;
int low = 0, high = 1e14, best = 0;
while (low <= high) {
int mid = (low + high) / 2;
auto [gain, segs] = compute(mid);
if (segs <= K) {
best = gain + mid * segs;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << best;
return 0;
}
# | 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... |