# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1165663 | Warinchai | Feast (NOI19_feast) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[300005];
int sum[300005];
int inf=1e18+5;
int n,k;
pair<int,int> solve(int l){
pair<int,int>best={0,0};
pair<int,int>ans={0,0};
for(int i=1;i<=n;i++){
pair<int,int>tans={sum[i]+best.first-l,best.second-1};
ans=max(ans,tans);
best=max(best,{ans.first-sum[i],ans.second});
}
return {ans.first,ans.second*-1};
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>ar[i];
sum[i]=sum[i-1]+ar[i];
}
int st=0,en=3e15+1,ans=0;
while(st<=en){
int m=(st+en)/2;
auto x=solve(m);
//cerr<<m<<" "<<x.first<<" "<<x.second<<"\n";