oj.uz

Submission #363233

# Submission time Handle Problem Language Result Execution time Memory
363233 2021-02-05T10:21:28 Z nicolaalexandra K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define DIMK 110
#define INF 2000000000
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;

    int mini = INF, 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]

    for (j=2;j<=k;j++)
        divide (1,n,1,n);

    /*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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -