oj.uz

Submission #487897

# Submission time Handle Problem Language Result Execution time Memory
487897 2021-11-17T01:15:16 Z SirCovidThe19th K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 844 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define inf (ll)1e18

const int mx = 2e5 + 5;

int n, k, A[mx]; stack<int> stk;

struct Node{ ll mnDP, vDP; int vRange; };

template<int sz> struct ST{
    Node seg[524288]; int lz[524288];
	
    inline Node comb(Node a, Node b){ 
        if (a.vDP + a.vRange > b.vDP + b.vRange) swap(a, b);
        a.mnDP = min(a.mnDP, b.mnDP);
        return a;
    }
    inline Node comb1(int i, int j){
        Node a = seg[i], b = seg[j];
        if (lz[i]) a.vDP = a.mnDP, a.vRange = lz[i];
        if (lz[j]) b.vDP = b.mnDP, b.vRange = lz[j];
        return comb(a, b);
    }
    inline void push(int l, int r, int i){
        if (!lz[i]) return;
        seg[i].vRange = lz[i];
        if (l != r) lz[i * 2] = lz[i * 2 + 1] = lz[i];
        lz[i] = 0;
    }
    inline void upd(int x, int y, ll vDP, int vR, int l = 0, int r = sz, int i = 1){
        push(l, r, i);
        if (l > y or r < x) return;
        if (l >= x and r <= y){ 
            if (vDP) seg[i].mnDP = seg[i].vDP = vDP; 
            if (vR) lz[i] = vR, push(l, r, i);
            return;
        }
        int mid = (l + r) / 2;
        upd(x, y, vDP, vR, l, mid, i * 2); upd(x, y, vDP, vR, mid + 1, r, i * 2 + 1);
        seg[i] = comb1(i * 2, i * 2 + 1);
    }
    inline Node query(int x, int y, int l = 0, int r = sz, int i = 1){
        push(l, r, i); 
        if (l > y or r < x) return {inf, inf, (int)1e9};
        if (l != r) seg[i] = comb1(i * 2, i * 2 + 1); //reupd
        if (l >= x and r <= y) return seg[i];
        int mid = (l + r) / 2; 
        return comb(query(x, y, l, mid, i * 2), query(x, y, mid + 1, r, i * 2 + 1));
    }
};ST<mx> dp[101];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k; 
	
    for (int j = 1; j <= k; j++) dp[j].upd(0, 0, inf, 0);
    for (int i = 1; i <= n; i++) dp[0].upd(i, i, inf, 0);

    for (int i = 1; i <= n; i++){
        cin >> A[i];

        while (!stk.empty() and A[stk.top()] < A[i]) stk.pop();
        int L = (stk.empty()) ? 0 : stk.top();

        for (int j = 1; j <= k; j++){
            dp[j - 1].upd(L, i - 1, 0, A[i]);
            Node ret = dp[j - 1].query(0, i - 1); 
            ll ans = ret.vDP + ret.vRange;
            dp[j].upd(i, i, ans, 0);

            if (i == n and j == k) cout<<ans<<endl;
        }
        stk.push(i);
    }  
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 716 KB Output is correct
11 Correct 0 ms 716 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 588 KB Output is correct
10 Correct 0 ms 588 KB Output is correct
11 Correct 0 ms 716 KB Output is correct
12 Incorrect 1 ms 844 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 716 KB Output is correct
11 Correct 0 ms 716 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 716 KB Output is correct
11 Correct 0 ms 716 KB Output is correct
12 Correct 0 ms 460 KB Output is correct
13 Incorrect 1 ms 844 KB Output isn't correct
14 Halted 0 ms 0 KB -