oj.uz

Submission #119734

# Submission time Handle Problem Language Result Execution time Memory
119734 2019-06-22T05:22:08 Z dolphingarlic K blocks (IZhO14_blocks) C++14
0 / 100
 197 ms 4668 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int dp[100001][101], segtree[400004], a[100001], n, k;

void build(int node = 1, int l = 1, int r = n) {
    if (l == r)
        segtree[node] = a[l];
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int query(int a, int b, int node = 1, int l = 1, int r = n) {
    if (l > b || r < a || a > b) return 0;
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(a, b, node * 2, l, mid),
               query(a, b, node * 2 + 1, mid + 1, r));
}

bool case1(int x, int y, int z, int i) {
    return dp[y][i - 1] - dp[x][i - 1] <= query(x + 1, z) - query(y + 1, z);
}

bool case2(int x, int y, int z, int i) {
    return dp[y][i - 1] - dp[x][i - 1] + query(y + 1, z) - query(x + 1, z) <=
           dp[z][i - 1] - dp[y][i - 1] + query(z + 1, z) - query(y + 1, z);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    build();

    FOR(i, 0, n + 1) fill(dp[i], dp[i] + k + 1, (int)1e8);
    dp[0][0] = 0;

    FOR(i, 1, k + 1) {
        deque<ll> q;
        q.push_back(i - 1);
        FOR(j, i, n + 1) {
            while (q.size() > 1 && case1(q[0], q[1], j, i)) {
                // cout << "YEET " << q[0] << ' ' << q[1] << ' ' << j << '\n';
                q.pop_front();
            }
            int x = q.front();
            // cout << x << ' ';
            dp[j][i] = dp[x][i - 1] + query(x + 1, j);
            while (q.size() > 1 && case2(q[q.size() - 2], q.back(), j, i))
                q.pop_back();
            q.push_back(j);

            // cout << i << ' ' << j << ' ' << dp[j][i] << '\n';
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 4668 KB Output isn't correct
2 Halted 0 ms 0 KB -