Submission #87268

#	Time	Username	Problem	Language	Result	Execution time	Memory
87268		Yaroslaff	K blocks (IZhO14_blocks)	C++14	100 / 100	196 ms	14684 KiB

blocks

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
//#define int ll
#define ld long double
#define null nullptr
#define endl '\n'

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int M = 1e9 + 7;
const int N = 1e5 + 7;

int n, k, x[N];
vector<int> res(N, M), curr;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#else
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
#endif
    cin >> n >> k;res[0] = 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int j = 0; j < k; j++){
        vector<int> mx, dp;
        curr.assign(N, M);
        for (int i = 0; i < n; i++){
            int cur = res[i];
            while (!mx.empty() && mx.back() < x[i]){
                cur = min(cur, dp.back());
                mx.pop_back();
                dp.pop_back();
            }
            if (mx.empty() || cur + x[i] < dp.back() + mx.back())
                mx.pb(x[i]), dp.pb(cur);
            if (i >= j) curr[i + 1] = mx.back() + dp.back();
        }
        res = curr;
    }
    cout << res[n];
    return 0;
}

Compilation message (stderr)

blocks.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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