#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
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];
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |