Submission #1094226

#TimeUsernameProblemLanguageResultExecution timeMemory
1094226Trisanu_DasFeast (NOI19_feast)C++17
100 / 100
96 ms10476 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second int n, k, a[300005]; pair<int, int> dp[300005]; pair<int, int> calc(int mid){ pair<int, int> curr(0,0); for(int i = 1; i <= n; i++){ dp[i] = max(dp[i - 1], {curr.ff + a[i] - mid, curr.ss + 1}); curr = max(curr, {dp[i].ff - a[i], dp[i].ss}); } return dp[n]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) a[i] += a[i - 1]; int l = 0, r = 3e14; while(l < r){ int mid = (l + r + 1) / 2; if(calc(mid).ss >= k) l = mid; else r = mid - 1; } cout << calc(l).ff + l * k << '\n'; }
#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...