Submission #38071

#	Time	Username	Problem	Language	Result	Execution time	Memory
38071		nickyrio	K blocks (IZhO14_blocks)	C++14	100 / 100	239 ms	45944 KiB

blocks

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 100100
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;

template<class X, class Y> inline void Max(X &x, Y y) { x = x > y ? x : y; }
template<class X, class Y> inline void Min(X &x, Y y) { x = x < y ? x : y; }
/*
dp[i][j] = min(dp[i - 1][k] + RMQ[k + 1][j]);

*/

int n, k, a[N];
int dp[111][N];

stack<int> st;

int main() {
    IO;
    scanf("%d %d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
    int mx = -1;
    FOR(i, 1, n) Max(mx, a[i]), dp[1][i] = mx; 
    FOR(j, 2, k) {
        while (!st.empty()) st.pop();
        st.push(j - 1);
        //dp[j][j] = dp[j - 1][j - 1] + a[j];
        FOR(i, j, n) {
            int best = 1e9;
            while (!st.empty() && a[st.top()] <= a[i]) {
                if (st.top() != j - 1) Min(best, dp[j][st.top()] + a[i] - a[st.top()]);
                Min(best, dp[j - 1][st.top()] + a[i]);
                st.pop();
            }
            if (!st.empty()) {
                if (st.top() != j - 1) Min(best, dp[j][st.top()]);
                Min(best, dp[j - 1][st.top()] + a[i]);
            }
            else Min(best, dp[j - 1][j - 1] + a[i]);
            dp[j][i] = best;
          //  cerr << j << ' ' << i << ' ' << best << endl;
            st.push(i);
        }
    }
    printf("%d", dp[k][n]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:31:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^
blocks.cpp:32:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^

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