#include <iostream>
using namespace std;
int rm[100005][20],log2[100005],n,k,a[100005];
long long d[100005][3];
int rmq(int x,int y){
return max(rm[x][log2[y-x+1]],rm[y-(1<<log2[y-x+1])+1][log2[y-x+1]]);
}
void dve(int j, int st, int dr,int splitl,int splitr) {
if(st > dr)
return;
int mj = (st + dr) >> 1;
long long x=(1LL<<50);
int splitmj=1;
for(int 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(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
rm[i][0]=a[i];
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
rm[i][j]= max(rm[i][j-1],rm[i+(1<<(j-1))][j-1]);
}
}
for(int i=2;i<=n;i++){
log2[i]=log2[i/2]+1;
}
for(int i=1;i<=n;i++){
d[i][1]=max(d[i-1][1],1LL*a[i]);
}
for(int j=2;j<=k;j++){
dve(j%2,1,n,1,n);
}
cout<<d[n][k%2]<<'\n';
return 0;
}
Compilation message
blocks.cpp:4:20: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
4 | int rm[100005][20],log2[100005],n,k,a[100005];
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 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 |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 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 |
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 |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 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 |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |