oj.uz

Submission #845794

# Submission time Handle Problem Language Result Execution time Memory
845794 2023-09-06T15:43:10 Z BamshooT K blocks (IZhO14_blocks) C++14
0 / 100
 7 ms 45144 KB 
#include <iostream>
#include <cstring>
#include <vector>

#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define fi first
#define se second
#define inf 1e9

using namespace std;

typedef pair <int, int> ii;

const int N = 1e5 + 9;
int n, k, a[N], dp[N][109], st[N << 2], L[N];

void build(int id, int l, int r){
    if (l == r){
        st[id] = dp[l][1];
        return;
    }
    int mid = l + r >> 1;
    build(id*2, l, mid); build(id*2 + 1, mid + 1, r);
    st[id] = min(st[id*2], st[id*2+1]);
}

void update(int id, int l, int r, int i, int val){
    if (i < l || r < i) return;
    if (l == r){
        st[id] = val;
        return;
    }
    int mid = l + r >> 1;
    update(id*2, l, mid, i, val); update(id*2 + 1, mid + 1, r, i, val);
    st[id] = min(st[id*2], st[id*2+1]);
}
int get(int id, int l, int r, int u, int v){
    if (v < l || r < u) return inf;
    if (u <= l && r <= v) return st[id];
    int mid = l + r >> 1;
    return min(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   // freopen("nhap.inp", "r", stdin);
    //freopen("xuat.out", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[1][1] = a[1];
    for (int i = 2; i <= n; ++i) dp[i][1] = max(dp[i-1][1], a[i]);
    for (int i = 1; i <= n; ++i)
       for (L[i] = i-1; L[i] && a[L[i]] <= a[i];) L[i] = L[L[i]];
    build(1, 1, n);
    FOR(t, 2, k)
        for (int i = t; i <= n; ++i) {
            /// dp[i][t] = min(dp[i][t], dp[i-1][t-1] + p);
            dp[i][t] = min(dp[L[i]][t], get(1, 1, n, max(L[i] + 1, t-1), i-1) + a[i]);
            update(1, 1, n, i, dp[i-1][t-1]);
        }
    cout << dp[n][k];
    return 0;
}

Compilation message

blocks.cpp: In function 'void build(int, int, int)':
blocks.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
blocks.cpp: In function 'void update(int, int, int, int, int)':
blocks.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = l + r >> 1;
      |               ~~^~~
blocks.cpp: In function 'int get(int, int, int, int, int)':
blocks.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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