oj.uz

Submission #363235

# Submission time Handle Problem Language Result Execution time Memory
363235 2021-02-05T10:25:35 Z nicolaalexandra K blocks (IZhO14_blocks) C++14
53 / 100
 18 ms 3180 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
18.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 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 0 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 492 KB Output is correct
35 Correct 1 ms 492 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 492 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 620 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Correct 1 ms 364 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 1 ms 364 KB Output is correct
47 Correct 1 ms 364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 492 KB Output is correct
50 Correct 1 ms 364 KB Output is correct
51 Correct 1 ms 492 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1 ms 1004 KB Output is correct
54 Correct 2 ms 1004 KB Output is correct
55 Correct 1 ms 748 KB Output is correct
56 Correct 1 ms 1004 KB Output is correct
57 Correct 1 ms 1004 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 0 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 492 KB Output is correct
35 Correct 1 ms 492 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 492 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 620 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Correct 1 ms 364 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 1 ms 364 KB Output is correct
47 Correct 1 ms 364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 492 KB Output is correct
50 Correct 1 ms 364 KB Output is correct
51 Correct 1 ms 492 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1 ms 1004 KB Output is correct
54 Correct 2 ms 1004 KB Output is correct
55 Correct 1 ms 748 KB Output is correct
56 Correct 1 ms 1004 KB Output is correct
57 Correct 1 ms 1004 KB Output is correct
58 Incorrect 18 ms 3180 KB Output isn't correct
59 Halted 0 ms 0 KB -