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;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int &x : a) cin >> x;
auto solve_lambda = [&](ll lambda) {
vector<pair<ll, int>> dp[2];
dp[0].resize(n);
dp[1].resize(n);
dp[0][0] = mp(0LL, 0);
dp[1][0] = mp(a[0] - lambda, 1);
for(int i = 1; i < n; ++i) {
dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
dp[1][i] = max(mp(dp[1][i-1].fi + a[i], dp[1][i-1].se), mp(dp[0][i-1].fi + a[i] - lambda, dp[0][i-1].se + 1));
}
return max(dp[0][n-1], dp[1][n-1]);
};
ll low = 0, high = 1e15;
while (high - low > 1) {
ll mid = (high + low) / 2;
if(solve_lambda(mid).se >= k) low = mid;
else high = mid;
}
debug(low);
auto [u, c] = solve_lambda(low);
debug(u);
debug(c);
cout << u + k * low << '\n';
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... |