# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1101411 | thanhhoang | K blocks (IZhO14_blocks) | C++14 | 1076 ms | 41804 KiB |
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;
const int N=1e5+53;
int n,k,a[N][20],b[N][102];
int get(int l,int r)
{
int o=log2(r-l+1);
return max(a[l][o],a[r-(1<<o)+1][o]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen("blocks.inp","r"))
{
freopen("blocks.inp","r",stdin);
freopen("blocks.out","w",stdout);
}
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i][0];
for(int i=1;i<=log2(n);i++)
for(int j=0;j+(1<<i)-1<=n;j++)
a[j][i]=max(a[j][i-1],a[j+(1<<i-1)][i-1]);
memset(b,0x3f,sizeof b);
b[0][0]=0;
for(int i=1;i<=k;i++)
for(int j=i;j<=n;j++)
for(int o=max(i,(j-10)*(n*k*n>1e8));o<=j;o++)
b[i][j]=min(b[i][j],b[i-1][o-1]+get(o,j));
cout<<b[k][n];
return 0;
}
Compilation message (stderr)
# | 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... |