Submission #1215683

#TimeUsernameProblemLanguageResultExecution timeMemory
1215683timeflewFeast (NOI19_feast)C++20
0 / 100
72 ms11844 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define all(x) x.begin(), x.end() const int mxN=3e5; ll a[mxN+1]; pair<ll, ll> dp[mxN+1][2]; ll n, k; pair<ll, ll> f(ll p) { dp[0][0]={0, 0}; dp[0][1]={a[0]-p, 1}; for(int i=1; i<n; i++) { dp[i][0]=max(dp[i-1][0], dp[i-1][1]); dp[i][1]=max(make_pair(dp[i-1][0].ff+a[i]-p, dp[i-1][0].ss+1), make_pair(dp[i-1][1].ff+a[i], dp[i-1][1].ss)); } return max(dp[n-1][0], dp[n-1][1]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>k; for(int i=0; i<n; i++) { cin>>a[i]; } ll l=-1e9, r=1e18; while(l<=r) { ll mid=(l+r)/2; if(f(mid).ss>=k) { l=mid+1; } else { r=mid-1; } } cout<<f(l).ff+l*k; return 0; } //rating below 2400 must be solved orzorzorz
#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...