제출 #789489

#제출 시각아이디문제언어결과실행 시간메모리
789489WarinchaiFeast (NOI19_feast)C++14
18 / 100
53 ms8024 KiB
#include<bits/stdc++.h> using namespace std; long long ar[300005]; long long sum[300005]; long long n,k; pair<long long,int> solve(long long l){ pair<long long,int>dp={0,0},best={0,0}; for(int i=1;i<=n;i++){ dp=max(dp,{sum[i]-l+best.first,best.second-1}); best=max(best,{dp.first-sum[i],dp.second}); } dp.second*=-1; return dp; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>k; long long sm=0; for(int i=1;i<=n;i++){ cin>>ar[i]; sm+=ar[i]; sum[i]=sm; } long long st=0,en=3e14+1; while(st<en){ long long m=(st+en)/2; pair<long long,int>tmp=solve(m); //cout<<m<<" "<<tmp.first<<" "<<tmp.second<<endl; if(tmp.second==k){ cout<<tmp.first+m*k; return 0; }else if(tmp.second<k){ en=m-1; }else{ st=m+1; } } }
#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...