#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+5;
const int oo=1e8+5;
int m;
int n,k;
int a[N];
int IT[N*8];
int F[N][105];
void build(int k,int l,int r){
if(l>r) return;
if(l==r){
IT[k]=a[l];
return;
}
int mid=(l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
IT[k]=max(IT[k*2],IT[k*2+1]);
}
int getmax(int k,int l,int r,int u,int v){
if(r<u||l>v)
return 0;
if(l>=u&&r<=v)
return IT[k];
int mid=(l+r)/2;
return max(getmax(k*2,l,mid,u,v),getmax(k*2+1,mid+1,r,u,v));
}
/*
void Solve(){
FOR(i,1,k) FOR(j,i,n)
F[i][j]=F[i-1][j-1]+getmax(1,1,n,j,n);
cout<<F[k][n];
}*/
int Try(int n,int k){
if(k==1) return getmax(1,1,m,1,n);
if(F[n][k]) return F[n][k];
int tmp=oo+5;
for(int i=n;i>=max(2,k);i--){
int t=getmax(1,1,m,i,n);
tmp=min(tmp,t+Try(i-1,k-1));
}
F[n][k]=tmp;
return F[n][k];
}
main(){
//freopen("blocks.in","r",stdin);
//freopen("blocks.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
FOR(i,1,n) cin>>a[i];
build(1,1,n);
m=n;
int t=Try(n,k);
cout<<Try(n,k);
}
Compilation message
blocks.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
blocks.cpp: In function 'int main()':
blocks.cpp:64:9: warning: unused variable 't' [-Wunused-variable]
int t=Try(n,k);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
672 KB |
Output is correct |
| 10 |
Correct |
2 ms |
680 KB |
Output is correct |
| 11 |
Correct |
2 ms |
812 KB |
Output is correct |
| 12 |
Correct |
2 ms |
812 KB |
Output is correct |
| 13 |
Correct |
4 ms |
812 KB |
Output is correct |
| 14 |
Correct |
4 ms |
812 KB |
Output is correct |
| 15 |
Correct |
2 ms |
812 KB |
Output is correct |
| 16 |
Correct |
3 ms |
812 KB |
Output is correct |
| 17 |
Correct |
2 ms |
812 KB |
Output is correct |
| 18 |
Correct |
4 ms |
812 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
812 KB |
Output is correct |
| 2 |
Correct |
2 ms |
812 KB |
Output is correct |
| 3 |
Correct |
2 ms |
816 KB |
Output is correct |
| 4 |
Correct |
2 ms |
820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
824 KB |
Output is correct |
| 6 |
Correct |
2 ms |
828 KB |
Output is correct |
| 7 |
Correct |
2 ms |
836 KB |
Output is correct |
| 8 |
Correct |
2 ms |
836 KB |
Output is correct |
| 9 |
Correct |
2 ms |
932 KB |
Output is correct |
| 10 |
Correct |
2 ms |
932 KB |
Output is correct |
| 11 |
Correct |
2 ms |
932 KB |
Output is correct |
| 12 |
Correct |
2 ms |
932 KB |
Output is correct |
| 13 |
Correct |
2 ms |
932 KB |
Output is correct |
| 14 |
Correct |
2 ms |
932 KB |
Output is correct |
| 15 |
Correct |
2 ms |
932 KB |
Output is correct |
| 16 |
Correct |
2 ms |
932 KB |
Output is correct |
| 17 |
Correct |
2 ms |
932 KB |
Output is correct |
| 18 |
Correct |
3 ms |
932 KB |
Output is correct |
| 19 |
Correct |
2 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
932 KB |
Output is correct |
| 2 |
Correct |
2 ms |
932 KB |
Output is correct |
| 3 |
Correct |
2 ms |
932 KB |
Output is correct |
| 4 |
Correct |
2 ms |
932 KB |
Output is correct |
| 5 |
Correct |
2 ms |
932 KB |
Output is correct |
| 6 |
Correct |
2 ms |
932 KB |
Output is correct |
| 7 |
Correct |
2 ms |
932 KB |
Output is correct |
| 8 |
Correct |
2 ms |
932 KB |
Output is correct |
| 9 |
Correct |
2 ms |
952 KB |
Output is correct |
| 10 |
Correct |
2 ms |
956 KB |
Output is correct |
| 11 |
Correct |
2 ms |
960 KB |
Output is correct |
| 12 |
Correct |
2 ms |
964 KB |
Output is correct |
| 13 |
Correct |
9 ms |
972 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1104 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1104 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1104 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1074 ms |
1592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
