Submission #1070833

#TimeUsernameProblemLanguageResultExecution timeMemory
1070833TAhmed33Feast (NOI19_feast)C++98
100 / 100
154 ms15236 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 3e5 + 25; ll a[MAXN], n, k; pair <ll, ll> eval (ll mid) { pair <ll, ll> dp[n + 1][2]; dp[1][0] = {0, 0}; dp[1][1] = {a[1] - mid, 1}; for (int i = 2; i <= n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); pair <ll, ll> g = {dp[i - 1][0].first + a[i] - mid, dp[i - 1][0].second + 1}; pair <ll, ll> h = {dp[i - 1][1].first + a[i], dp[i - 1][1].second}; dp[i][1] = max(g, h); dp[i][0] = max(dp[i][0], {0ll, 0ll}); dp[i][1] = max(dp[i][1], {a[i] - mid, 1ll}); } return max({dp[n][0], dp[n][1], {0ll, 0ll}}); } void solve () { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } ll l = 0, r = 1e18, ans = 0; while (l <= r) { ll mid = (l + r) / 2; if (eval(mid).second >= k) { l = mid + 1; ans = mid; } else { r = mid - 1; } } cout << eval(ans).first + ans * k << '\n'; } signed main () { ios::sync_with_stdio(0); cin.tie(0); int tc = 1; //cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...