This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
const int inf=1e9;
using i64=long long;
int n;
vector<int>a;
pair<i64 , int> test(const int lambda)
{
pair<i64,int>sol={0,0};
pair<i64,int> last={-1e18,0};
for(int i=0;i<n;i++)
{
if(sol.first-lambda > last.first || (sol.first-lambda == last.first && sol.second<last.second))
{
last={sol.first+a[i]-lambda, sol.second+1};
}
else
{
last.first+=a[i];
}
if(sol.first<last.first || (sol.first==last.first && sol.second>last.second))
{
sol=last;
}
}
return sol;
}
main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int k;
cin>>n>>k;
a.resize(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int st=0,dr=inf;
i64 rez=-1e18;
while(st<=dr)
{
int m=(st+dr)/2;
auto xd=test(m);
if(xd.second < k)
{
dr=m-1;
rez=xd.first+1LL*k*m;
}
else
{
st=m+1;
rez=xd.first+1LL*k*m;
}
}
cout<<rez;
return 0;
}
Compilation message (stderr)
feast.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
33 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |