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 <iostream>
using namespace std;
long long rm[100005][20],log2[100005],n,k,a[100005];
long long d[100005][3];
long long rmq(long long x,long long y){
return max(rm[x][log2[y-x+1]],rm[y-(1<<log2[y-x+1])+1][log2[y-x+1]]);
}
void dve(long long j, long long st, long long dr,long long splitl,long long splitr) {
if(st > dr)
return;
long long mj = (st + dr) >> 1;
long long x=(1LL<<50);
long long splitmj=1;
for(long long st=splitl;st<=min(splitr,mj);st++){
if(x > d[st][(j+1)%2]+rmq(st+1,mj)) {
x=d[st][(j+1)%2]+rmq(st+1,mj);
splitmj = st;
}
}
d[mj][j]=x;
dve(j,st,mj-1,splitl,splitmj);
dve(j,mj+1,dr,splitmj,splitr);
}
int main()
{
///d[i][j]-costul daca impart primele i elemente in j secv
cin>>n>>k;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
for(long long i=1;i<=n;i++){
rm[i][0]=a[i];
}
for(long long j=1;(1<<j)<=n;j++){
for(long long i=1;i<=n-(1<<j)+1;i++){
rm[i][j]= max(rm[i][j-1],rm[i+(1<<(j-1))][j-1]);
}
}
for(long long i=2;i<=n;i++){
log2[i]=log2[i/2]+1;
}
for(long long i=1;i<=n;i++){
d[i][1]=max(d[i-1][1],1LL*a[i]);
}
for(long long j=2;j<=k;j++){
dve(j%2,1,n,1,n);
}
cout<<d[n][k%2];
return 0;
}
Compilation message (stderr)
blocks.cpp:4:26: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
4 | long long rm[100005][20],log2[100005],n,k,a[100005];
| ^~~~
# | 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... |