# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1258831 | phtung | Feast (NOI19_feast) | C++20 | 259 ms | 21572 KiB |
#include <bits/stdc++.h>
using namespace std;
#define name "IO"
#define int long long
const long long INF = (long long)1e18;
const int MAXN = 3e5 + 5;
const long double EPS = 1e-6;
int n, k, a[MAXN];
pair<long double,int> dp[MAXN][2];
bool check(long double lambda) {
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]);
auto v1 = make_pair(dp[i-1][1].first + a[i], dp[i-1][1].second);
auto v2 = make_pair(dp[i-1][0].first + a[i] - lambda, dp[i-1][0].second + 1);
dp[i][1] = max(v1, v2);
}
return max(dp[n][0], dp[n][1]).second >= k;
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
long double low = 0, high = 1e12;
while (high - low > EPS) {
long double mid = (low + high) / 2;
if (check(mid)) low = mid;
else high = mid;
}
long double lambda = low;
check(lambda);
auto best = max(dp[n][0], dp[n][1]);
cout << (long long)round(lambda * k + best.first) << "\n";
}
signed main()
{
if (fopen (name".INP", "r"))
{
freopen (name".INP", "r", stdin);
freopen (name".OUT", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
clock_t start = clock();
int t = 1;
while(t--) solve();
std::cerr << "Time: " << clock() - start << "ms\n";
return 0;
}
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... |