Submission #1103167

#TimeUsernameProblemLanguageResultExecution timeMemory
11031670pt1mus23Feast (NOI19_feast)C++14
100 / 100
127 ms20048 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int #define ins insert #define pb push_back #define endl '\n' #define putr(x) cout<<x<<endl;return; #define all(x) x.begin(),x.end() // mt19937 rng(time(0)); const int mod = 1e9 +9, sze = 5e5 +23, inf = LLONG_MAX, LL = 30; // Lagrangian Relaxation - Usaco Guide pair<int,int> dp[2][sze]; int arr[sze]; int n; void clc(int mid){ dp[1][0]={arr[0]-mid,1}; dp[0][0]={0,0}; for(int i=1;i<n;i++){ dp[0][i]=max(dp[0][i-1],dp[1][i-1]); dp[1][i]=max( make_pair(dp[0][i-1].first + arr[i]-mid,dp[0][i-1].second +1), make_pair(dp[1][i-1].first + arr[i],dp[1][i-1].second) ); } } void rush(){ int k; cin>>n>>k; for(int i=0;i<n;i++){ cin>>arr[i]; } int l =0; int r = 1e18; int ans=0; while(l<=r){ int mid = (l+r)/2; clc(mid); auto mx = max(dp[1][n-1],dp[0][n-1]); if(mx.second >=k ){ ans=mid; l=mid+1; } else{ r = mid-1; } } clc(ans); auto mx = max(dp[1][n-1],dp[0][n-1]); putr( k*ans + mx.first ); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin>>tt; while(tt--){ rush(); } 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...