Submission #1248007

#TimeUsernameProblemLanguageResultExecution timeMemory
1248007simplemind_31Feast (NOI19_feast)C++20
100 / 100
132 ms12176 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,k; vector<ll> nums; pair<ll,ll> solve(ll penal){ pair<ll,ll> dp[n][2]; dp[0][0]={0,0}; dp[0][1]={nums[0]-penal,1}; for(int i=1;i<n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]); pair<ll,ll> op1={dp[i-1][0].first+nums[i]-penal,dp[i-1][0].second+1}; pair<ll,ll> op2={dp[i-1][1].first+nums[i],dp[i-1][1].second}; dp[i][1]=max(op1,op2); } return max(dp[n-1][0],dp[n-1][1]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> k; nums.resize(n); for(ll i=0;i<n;i++){ cin >> nums[i]; } ll l=0,r=1e18; while(l<r){ ll mid=(l+r+1)>>1; // mayor mid=menor k if(solve(mid).second>=k){ l=mid; }else{ r=mid-1; } } pair<ll,ll> res=solve(l); cout << res.first+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...