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;
typedef long long ll;
const ll INF=1e17;
ll n,k,v[300005];
struct date
{
ll val,l,r;
};
date dp[300005][2];
date combine(date a, date b)
{
if(a.val>b.val)
return a;
if(a.val<b.val)
return b;
a.l=min(a.l,b.l);
a.r=max(a.r,b.r);
return a;
}
date calc(ll cost)
{
dp[0][0]={0,0,0};
dp[0][1]={-INF,0,0};
for(int i=1;i<=n;i++)
{
dp[i][0]=combine(dp[i-1][0],dp[i-1][1]);
date a=dp[i-1][0];
a.l++;
a.r++;
a.val+=v[i]-cost;
dp[i][1]=a;
a=dp[i-1][1];
a.val+=v[i];
dp[i][1]=combine(dp[i][1],a);
a=dp[i-1][1];
a.l++;
a.r++;
a.val+=v[i]-cost;
dp[i][1]=combine(dp[i][1],a);
}
return combine(dp[n][0],dp[n][1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(ll i=1;i<=n;i++)
cin>>v[i];
ll st=-1e12;
ll dr=1e12;
while(st<=dr)
{
ll mij=(st+dr)/2;
date rez=calc(mij);
if(rez.l<=k&&rez.r>=k)
{
cout<<max(0LL,rez.val+k*mij);
return 0;
}
if(rez.l>k)
st=mij+1;
else
dr=mij-1;
}
assert(false);
return 0;
}
# | 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... |