Submission #276451

#	Time	Username	Problem	Language	Result	Execution time	Memory
276451		mosiashvililuka	K blocks (IZhO14_blocks)	C++14	100 / 100	185 ms	172408 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,fen[1000009],f[100009],k[100009];
long long dp[100009][109],pr[100009][109];
stack <int> s;
void upd(int q, int w){
    while(q<=1000002){
        fen[q]=max(fen[q],w);
        q=q+(q&(-q));
    }
}
int read(int q){
    int jm=0;
    while(q>=1){
        if(jm<fen[q]) jm=fen[q];
        q=q-(q&(-q));
    }
    return jm;
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    /*printf("%d%d",&a,&b);
    scanf("\n");*/
    cin>>a>>b;
    for(i=1; i<=a; i++){
        cin>>f[i];
        //scanf("%d",&f[i]);
        //k[i]=read(1000001-f[i]);
        //cout<<k[i]<<" ";
        //upd(1000001-f[i]+1,i);
    }
    //cout<<endl;
    zx=0;
    for(i=0; i<=a; i++){
        for(j=0; j<=b; j++) pr[i][j]=999999999999999999LL;
        for(j=0; j<=b; j++) dp[i][j]=999999999999999999LL;
    }
    dp[0][0]=0;zx=0;
    for(i=1; i<=a; i++){
        while(s.size()>0&&f[s.top()]<f[i]){
            for(j=1; j<b; j++){
                pr[i][j]=min(pr[i][j],pr[s.top()][j]-f[s.top()]+f[i]);
            }
            s.pop();
        }
        if(s.size()>0){
            for(j=1; j<b; j++){
                pr[i][j]=min(pr[i][j],pr[s.top()][j]);
            }
        }
        for(j=1; j<b; j++){
            pr[i][j]=min(pr[i][j],dp[i-1][j]+f[i]);
        }
        for(j=2; j<=b; j++){
            dp[i][j]=dp[i-1][j-1]+f[i];
            if(dp[i][j]>pr[i][j-1]) dp[i][j]=pr[i][j-1];
        }
zx=max(zx,f[i]);
dp[i][1]=zx;
        s.push(i);
    }
    //cout<<pr[1][1]<<endl;
    cout<<dp[a][b];
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47