Submission #1211123

#TimeUsernameProblemLanguageResultExecution timeMemory
1211123ballsFeast (NOI19_feast)C++20
100 / 100
166 ms16844 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int MaxN = 3e5 + 7; int a[MaxN], n, k; pair<int, int> dp[MaxN][3]; pair<int, int> calc(int x) { dp[1][0] = {0, 0}; dp[1][1] = {a[1] - x, 1}; for (int i = 2; i <= n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - x, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second)); } return max(dp[n][0], dp[n][1]); } signed main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } int l = 0, r = 1e18; while (l < r) { int mid = (l + r + 1) / 2; if (calc(mid).second >= k) { l = mid; } else { r = mid - 1; } } cout << calc(l).first + l * k; }
#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...