oj.uz

Submission #119738

# Submission time Handle Problem Language Result Execution time Memory
119738 2019-06-22T06:00:32 Z dolphingarlic K blocks (IZhO14_blocks) C++14
0 / 100
 138 ms 4608 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)1e7);
    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();
            int 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 Incorrect 3 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 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 #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 138 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -