# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
440784 | dongliu0426 | Feast (NOI19_feast) | C++14 | 1085 ms | 20208 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;
const int N = 300000;
const long long INF = (long long) 300000 * 1000000000;
const long double EPS = 1e-6;
int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];
bool 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;
};
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
long double lower = 0, upper = INF;
while (lower + EPS < upper) {
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... |