Submission #363235

#	Time	Username	Problem	Language	Result	Execution time	Memory
363235		nicolaalexandra	K blocks (IZhO14_blocks)	C++14	53 / 100	18 ms	3180 KiB

blocks

#include <bits/stdc++.h>
#define DIM 100010
#define DIMK 110
#define INF 2000000000000000000LL
using namespace std;

int v[DIM],rmq[20][DIM],p[DIM];
long long dp[DIMK][DIM];
int n,k,i,j,t;

int get_min (int x, int y){
    int nr = p[y-x+1];
    return max (rmq[nr][x],rmq[nr][y-(1<<nr)+1]);
}

void divide (int st, int dr, int opt_st, int opt_dr){
    if (st > dr)
        return;
    int mid = (st+dr)>>1;

    long long mini = INF; int opt_mid = 0;
    for (int i=opt_st;i<=min(mid-1,opt_dr);i++){
        int val = get_min (i+1,mid);
        if (dp[j-1][i] + val < mini){
            mini = dp[j-1][i] + val;
            opt_mid = i;
        }
    }

    dp[j][mid] = mini;

    divide (st,mid-1,opt_st,opt_mid);
    divide (mid+1,dr,opt_mid,opt_dr);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=n;i++){
        cin>>v[i];
        rmq[0][i] = v[i];
    }

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= n)
                rmq[i][j] = max (rmq[i][j],rmq[i-1][j + (1<<(i-1))]);
        }

    for (i=2;i<=n;i++)
        p[i] = p[i/2] + 1;

    for (i=1;i<=k;i++)
        for (j=1;j<=n;j++)
            dp[i][j] = INF;

    int maxi = 0;
    for (i=1;i<=n;i++){
        maxi = max (maxi,v[i]);
        dp[1][i] = maxi;
    }

    /// dp[j][i] <= dp[j][i+1]

    if (n > 100){
        for (j=2;j<=k;j++)
            divide (1,n,1,n);
    } else {
        for (j=2;j<=k;j++){
            for (i=j;i<=n;i++){
                /// dp[j][i] = min (dp[k][i] + max(k+1..i))
                int maxi = 0;
                for (t=i;t>1;t--){
                    maxi = max (maxi,v[t]);
                    dp[j][i] = min (dp[j][i],dp[j-1][t-1] + maxi);
                }}}}

    cout<<dp[k][n];

    return 0;
}

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