Submission #471399

#	Time	Username	Problem	Language	Result	Execution time	Memory
471399		xhuy8248	K blocks (IZhO14_blocks)	C++14	100 / 100	179 ms	1892 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ii pair <int, int>
#define ST first
#define ND second
#define TASK "XHUY"

const int N = 1e5 + 5;

int n, k, a[N], dP[N], M[N];

int main()
{
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    FOR(i, 1, n)
        cin >> a[i], dP[i] = max(dP[i - 1], a[i]);
    FOR(i, 2, k)
    {
        stack <ii> st;
        FOR(j, i, n)
            M[j] = dP[j - 1];
        FOR(j, i, n)
        {
            while (!st.empty() && a[st.top().ND] <= a[j])
            {
                M[j] = min(M[j], st.top().ST);
                st.pop();
            }
            dP[j] = M[j] + a[j];
            if (!st.empty())
                dP[j] = min(dP[j], dP[st.top().ND]);
            st.push({M[j], j});
        }
    }
    cout << dP[n];
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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