# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
440011 | dongliu0426 | Feast (NOI19_feast) | C++14 | 506 ms | 20292 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define N 300000
#define INF 0x3f3f3f3f3f3f3f3f
int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];
int main() {
scanf("%d%d", &n, &k);
long long sum = 0;
for (int i = 1; i <= n; ++i)
scanf("%d", a + i), sum += a[i];
auto check = [&](long double penalty) {
dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0};
for (int i = 1; i <= n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second),
make_pair(dp[i - 1][0].first + a[i] - penalty, dp[i - 1][0].second + 1));
}
return max(dp[n][0], dp[n][1]).second >= k;
};
long double lower = 0, upper = sum;
for (int it = 0; it < 100; ++it) {
long double mid = (lower + upper) / 2;
if (check(mid)) {
lower = mid;
} else {
upper = mid;
}
}
long double penalty = lower;
check(penalty);
printf("%lld\n", (long long) round(penalty * k + max(dp[n][0], dp[n][1]).first));
}
Compilation message (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... |