Submission #171805

#	Time	Username	Problem	Language	Result	Execution time	Memory
171805		ne4eHbKa	K blocks (IZhO14_blocks)	C++17	18 / 100	1006 ms	19312 KiB

blocks

//{ <defines>
#ifndef _LOCAL
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#endif

#include <bits/stdc++.h>
using namespace std;

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int(x.size())
#define pw(x) (1 << (x))
#define PW(x) (1ll << (x))
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset(x, y, sizeof x)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

const int oo = 2e9;
const ll OO = 4e18;
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int md = 0x3b800001;
const int MD = 1e9 + 7;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//} </defines>
const int N = 1e5 + 5;
const int LG = 18;

int n, k, a[N], lg[N], st[LG][N], c[N];

inline int mx(int l, int r) {
    int f = lg[r - l + 1];
    re max(st[f][l], st[f][r - pw(f) + 1]);
}

struct tree {
    tree *l, *r;
    int v, p;
    tree(int tl = 0, int tr = n - 1): l(r = 0), v(oo), p(0) {
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
        }
    }
    inline void push() {
        ifn(p) re;
        if(l) l -> p += p;
        if(r) r -> p += p;
        if(v < oo) v += p;
        p = 0;
    }
    void assign(int i, int p, int tl = 0, int tr = n - 1) {
        push();
        if(tl == tr) re void(v = p);
        int tm = (tl + tr) >> 1;
        i <= tm
            ? l -> assign(i, p, tl, tm)
            : r -> assign(i, p, tm + 1, tr);
        v = min(l -> v, r -> v);
    }
    int req(int ql, int qr, int tl = 0, int tr = n - 1) {
        push();
        if(ql == tl && qr == tr) re v;
        if(ql > qr) re oo;
        int tm = (tl + tr) >> 1;
        re min(l -> req(ql, min(tm, qr), tl, tm),
               r -> req(max(ql, tm + 1), qr, tm + 1, tr));
    }
    void clear() {
        if(l) l -> clear();
        if(r) r -> clear();
        v = oo; p = 0;
    }
    void add(int pp, int ql, int qr, int tl = 0, int tr = n - 1) {
        if(ql == tl && qr == tr) re (p += pp, push());
        push();
        if(ql > qr) re;
        int tm = (tl + tr) >> 1;
        l -> add(pp, ql, min(tm, qr), tl, tm);
        r -> add(pp, max(ql, tm + 1), qr, tm + 1, tr);
        v = min(l -> v, r -> v);
    }
};

void solve() {
    cin >> n >> k;
    fo(n) cin >> a[i];

    tree t = *new tree();

    copy(a, a + n, st[0]);
    fo(n + 1) lg[i] = i ? lg[i - 1] + (pw(lg[i - 1] + 1) <= i) : 0;
    fo(LG) if(i) for(int j = 0; j + pw(i) - 1 < n; ++j) st[i][j] = max(st[i - 1][j], st[i - 1][j + pw(i - 1)]);

    int dp[k][n];

    fo(n) dp[0][i] = mx(0, i);

    fr(j, k) if(j) {
        t.clear();
        vi f;
        fo(n) {
            dp[j][i] = oo;
            if(i < j) continue;
            for(; !f.empty() && a[f.back()] <= a[i]; f.pop_back()) {
                t.add(a[i] - a[f.back()], f.size() == 1 ? 0 : f[sz(f) - 2] + 1, i - 1);
            }
            f.pb(i);
            t.assign(i, dp[j - 1][i - 1] + a[i]);
            dp[j][i] = t.v;
//            fr(p, n) cerr << t.req(p, p) << (p == n - 1 ? '\n' : ' ');
        }
    }

#ifdef _LOCAL
    int ch[k][n];
    fo(n) ch[0][i] = mx(0, i);
    fr(j, k) if(j) {
        fo(n) {
            ch[j][i] = oo;
            if(i < j) continue;
            fr(t, i) umin(ch[j][i], ch[j - 1][t] + mx(t + 1, i));
        }
    }
    fo(k) fr(j, n) if((dp[i][j] >= oo ? -1 : dp[i][j]) != (ch[i][j] >= oo ? -1 : ch[i][j])) cerr << "srak\n";

//    fo(k) fr(j, n) cerr << (dp[i][j] >= oo ? -1 : dp[i][j]) << (j == n - 1 ? '\n' : ' ');
//    fo(k) fr(j, n) cerr << (ch[i][j] >= oo ? -1 : ch[i][j]) << (j == n - 1 ? '\n' : ' ');
#endif


    cout << dp[k - 1][n - 1] << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    fo(tests) {
		cerr << "case #" << i+1 << endl;
		solve();
	}
#else
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
#endif
	return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 18 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47