Submission #1212376

#TimeUsernameProblemLanguageResultExecution timeMemory
1212376nmhungFeast (NOI19_feast)C++20
100 / 100
117 ms12276 KiB
#include <bits/stdc++.h> #define mp make_pair #define int long long #define pii pair<int,int> #define fi first #define se second using namespace std; const int mod=1e9 + 7; const int maxN=5e5+7; int n,k,a[maxN]; pii dp[2][maxN]; pii sol(int lmb) { dp[0][0]={0,0}; dp[1][0]={-lmb,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[0][i-1].fi+a[i]-lmb,dp[0][i-1].se+1),mp(dp[1][i-1].fi+a[i],dp[1][i-1].se)); } return max(dp[0][n],dp[1][n]); } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); cin>>n>>k; for(int i=1; i<=n; i++) cin>>a[i]; int l=0,r=1e18,ans=0; while(l<=r) { int mid=(l+r)/2; if(sol(mid).se>=k) { ans=mid; l=mid+1; } else r=mid-1; } cout<<sol(ans).fi+ans*k<<endl; return 0; }
#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...