# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1101543 | thanhhoang | K blocks (IZhO14_blocks) | C++14 | 277 ms | 49548 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],b[102][N],c[N],e[N],f[N][20];
stack<int>d;
void build(int oo)
{
for(int i=0;i<=n;i++) f[i][0]=b[oo][i];
for(int i=1;(1 << i) <= n;i++)
for(int j=0;j+(1<<i)-1<=n;j++)
f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]);
}
int get(int l,int r)
{
if (l > r) return 1e9;
int o=__lg(r-l+1);
return min(f[l][o],f[r-(1<<o)+1][o]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen("cc.inp","r"))
{
freopen("cc.inp","r",stdin);
freopen("cc.out","w",stdout);
}
cin>>n>>k;
a[0]=1e9;
d.push(0);
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(a[d.top()]<=a[i]) d.pop();
c[i]=d.top();
d.push(i);
}
memset(b,0x3f,sizeof b);
b[0][0]=0;
for(int i=1;i<=k;i++)
{
build(i-1);
for(int j=1;j<=n;j++)
b[i][j]=min(b[i][c[j]],get(c[j],j-1)+a[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... |