Submission #1255734

#TimeUsernameProblemLanguageResultExecution timeMemory
1255734namhhFeast (NOI19_feast)C++20
100 / 100
98 ms12104 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second const int N = 3e5+5; int n,k,a[N]; pii dp[N][2]; pii check(int mid){ 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]); pii c1 = {dp[i-1][0].fi+a[i]-mid,dp[i-1][0].se+1}; pii c2 = {dp[i-1][1].fi+a[i],dp[i-1][1].se}; dp[i][1] = max(c1,c2); } return max(dp[n][0],dp[n][1]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; int l = 0; int r = 1e14; while(l <= r){ int mid = (l+r)/2; if(check(mid).se > k) l = mid+1; else r = mid-1; } cout << check(l).fi+k*l; }
#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...