Submission #294667

#	Time	Username	Problem	Language	Result	Execution time	Memory
294667		phathnv	K blocks (IZhO14_blocks)	C++11	0 / 100	2 ms	384 KiB

blocks

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int K = 101;
const int INF = 1e9;

int n, k, h[N];

int top, dp[K][N];
ii St[N];

int main(){
    freopen("block.in", "r", stdin);
    freopen("block.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> h[i];

    dp[1][1] = h[1];
    for(int i = 2; i <= n; i++)
        dp[1][i] = max(dp[1][i - 1], h[i]);
    for(int c = 2; c <= k; c++){
        top = 0;
        h[c - 1] = INF;
        dp[c][c - 1] = INF;
        St[++top] = mp(c - 1, dp[c - 1][c - 1]);
        for(int i = c; i <= n; i++){
            while (h[i] >= h[St[top].X]){
                St[top - 1].Y = min(St[top - 1].Y, St[top].Y);
                top--;
            }
            dp[c][i] = min(dp[c][St[top].X], St[top].Y + h[i]);
            St[++top] = mp(i, dp[c - 1][i]);
        }
    }

    cout << dp[k][n];

    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     freopen("block.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     freopen("block.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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