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 int long long
#define fi first
#define se second
#define mp make_pair
#define stMx(a,b) a = max(a,b)
typedef pair<int,int> ii;
#define REP(i, a, b) for(int i = a; i < b; i++)
int32_t main() {
int N, K; cin >> N >> K; int A[N+1]; A[0]=0;
REP(i,1,N+1) {
cin>>A[i];
A[i]+=A[i-1];
}
ii dp[N+1];
int l = -1, h = 300000000000005;
while(h-l>1){
dp[0]=mp(0,0);
int lambda = (l+h)/2;
ii best = mp(0,0);
REP(i,1,N+1) {
dp[i]=max(dp[i-1],mp(A[i]+best.fi-lambda,best.se-1));
stMx(best,mp(dp[i].fi-A[i],dp[i].se));
}
if(dp[N].se>=-1*K) h=lambda;
else l=lambda;
}
ii best = mp(0,0);
REP(i,1,N+1) {
dp[i]=max(dp[i-1],mp(A[i]+best.fi-h,best.se-1));
stMx(best,mp(dp[i].fi-A[i],dp[i].se));
}
cout << dp[N].fi+h*K;
}
# | 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... |