제출 #171860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171860		ne4eHbKa	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	1077 ms	5248 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], v[N], p[N], f[N];

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

void fupd(int i, int v) {for(i = N - i - 1; i < N; i += i & -i) umin(f[i], v);}
int fget(int i) {int v = oo; for(i = N - i - 1; i; i -= i & -i) umin(v, f[i]); re v;}

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

    sort(p, p + n, [&] (int x, int y) {re a[x] < a[y];});
    fo(n) v[p[i]] = i ? v[p[i - 1]] + (a[p[i - 1]] != a[p[i]]) : 1;

    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)]);

    if(k == 1) re void(cout << mx(0, n - 1) << endl);

    fo(n) {
        int l = 1, r = i + 1;
        while(l < r) {
            int m = (l + r + 1) >> 1;
            mx(i - m, i - 1) >= a[i]
                ? r = m - 1
                : l = m;
        }
        c[i] = l;
    }

    int dp[k - 1][n];
    fo(n) dp[0][i] = mx(0, i);

    fo(k - 1) if(i) {
        clr(f, 127);
        fr(j, n) {
            dp[i][j] = fget(v[j]);
            if(j < i) continue;
            if(j && a[j - 1] >= a[j]) umin(dp[i][j], dp[i][j - 1]);
            for(int p = j - c[j]; p < j; ++p) if(p >= 0)
                umin(dp[i][j], dp[i - 1][p] + a[j]);
            fupd(v[j], dp[i][j]);
        }
    }

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

    int ans = oo;

    fo(n - 1) umin(ans, dp[k - 2][i] + mx(i + 1, n - 1));

    cout << ans << 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: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47