Submission #1209997

#TimeUsernameProblemLanguageResultExecution timeMemory
1209997tuankhang13Feast (NOI19_feast)C++20
100 / 100
151 ms12172 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second #define pii pair<int,int> #define vc vector<vector<int>> using namespace std; const int MOD=1e9+7; const int N=3e5+5; int a[N]; pii solve(int n,int lb){ pii dp[n][2]; for(int i=0;i<n;++i){ dp[i][1]=dp[i][0]={-1e18,0}; } dp[0][0]={0,0}; dp[0][1]={a[0]-lb,1}; for(int i=1;i<n;++i){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]); pii dp1={dp[i-1][0].fi+a[i]-lb,dp[i-1][0].se+1}; pii dp2={dp[i-1][1].fi+a[i],dp[i-1][1].se}; dp[i][1]=max(dp1,dp2); } return max(dp[n-1][1],dp[n-1][0]); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; for(int i=0;i<n;++i)cin>>a[i]; int l=0; int r=1e18; int ld=0; while(l<=r){ int mid=(l+r)/2; pii tmp=solve(n,mid); if(tmp.se>=k){ ld=mid; l=mid+1; } else { r=mid-1; } } pii res=solve(n,ld); cout<<res.fi+ld*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...