This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define INPFILE "FEAST.INP"
#define OUTFILE "FEAST.OUT"
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
using lli = long long int;
template <class X, class Y> inline bool maximise(X& a, Y b) { return a < b ? a = b, true : false; }
template <class T, class F>
T BINARY_SEARCH(T l, T r, const F& f) {
T ans = r + 1;
while (l <= r) {
T m = (l + r) >> 1;
bool upd;
int status;
tie(upd, status) = f(m);
if (upd)
ans = m;
if (status == 0)
return ans;
if (status == -1)
r = m - 1;
if (status == +1)
l = m + 1;
}
return ans;
}
const int MAX = 3e5 + 5;
const lli INF = 1e14;
int N, K;
int a[MAX];
lli dp[MAX][2];
int cnt[MAX][2];
int solve(lli cost) {
for (int j : {0, 1}) {
fill(dp[j], dp[j] + N + 1, -INF);
fill(cnt[j], cnt[j] + N + 1, 0);
}
dp[0][0] = 0;
dp[0][1] = -INF;
for (int i = 0; i < N; i++) {
int x = a[i + 1];
if (dp[i][0] > -INF) {
if (maximise(dp[i + 1][0], dp[i][0]))
cnt[i + 1][0] = cnt[i][0];
if (maximise(dp[i + 1][1], dp[i][0] + x - cost))
cnt[i + 1][1] = cnt[i][0] + 1;
}
if (dp[i][1] > -INF) {
if (maximise(dp[i + 1][0], dp[i][1]))
cnt[i + 1][0] = cnt[i][1];
if (maximise(dp[i + 1][1], dp[i][1] + x))
cnt[i + 1][1] = cnt[i][1];
}
}
return cnt[N][max_element(dp[N], dp[N] + 2) - dp[N]];
}
int main(void) {
if (fopen(INPFILE, "r")) {
freopen(INPFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++)
cin >> a[i];
lli cost = BINARY_SEARCH(0LL, +INF, [&] (lli x) -> pair <bool, int> {
int acum = solve(x);
if (acum == K)
return mp(true, 0);
if (acum <= K)
return mp(true, -1);
if (acum > K)
return mp(false, +1);
assert(0);
});
assert(solve(cost) == K);
lli ans = *max_element(dp[N], dp[N] + 2) + K * cost;
cout << ans << '\n';
return 0-0;
}
Compilation message (stderr)
feast.cpp: In function 'int main()':
feast.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen(INPFILE, "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
feast.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(OUTFILE, "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |