oj.uz

Submission #119739

# Submission time Handle Problem Language Result Execution time Memory
119739 2019-06-22T06:01:22 Z dolphingarlic K blocks (IZhO14_blocks) C++14
0 / 100
 222 ms 8676 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
ll dp[100001][101], segtree[400004], a[100001], n, k;
 
void build(ll node = 1, ll l = 1, ll r = n) {
    if (l == r)
        segtree[node] = a[l];
    else {
        ll 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]);
    }
}
 
ll query(ll a, ll b, ll node = 1, ll l = 1, ll r = n) {
    if (l > b || r < a || a > b) return 0;
    if (l >= a && r <= b) return segtree[node];
    ll mid = (l + r) / 2;
    return max(query(a, b, node * 2, l, mid),
               query(a, b, node * 2 + 1, mid + 1, r));
}
 
bool case1(ll x, ll y, ll z, ll i) {
    return dp[y][i - 1] - dp[x][i - 1] < query(x + 1, z) - query(y + 1, z);
}
 
bool case2(ll x, ll y, ll z, ll 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_MAX);
    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)) q.pop_front();
            ll x = q.front();
            dp[j][i] = dp[x][i - 1] + query(x + 1, j);
            while (q.size() > 1 && case2(q[q.size() - 2], q[q.size() - 1], j, i))
                q.pop_back();
            q.push_back(j);
        }
    }
    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 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Incorrect 2 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.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 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Incorrect 2 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 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 222 ms 8676 KB Output isn't correct
2 Halted 0 ms 0 KB -