Submission #1292535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292535		adscoding	K blocks (IZhO14_blocks)	C++20	100 / 100	113 ms	3576 KiB

blocks

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) cerr << "[ " << #__VA_ARGS__ << " ] = ", debug(__VA_ARGS__)
template<typename T> void debug(T x) { cerr << x << '\n'; }
template<typename T, typename... Args> void debug(T x, Args... args) { cerr << x << " , "; debug(args...); }

// ------------------------------------------------------------------------------------------------------------------------

const int maxn = 1e5 + 3;
int n, K, a[maxn];
ll dp_before[maxn], dp_cur[maxn], minF[maxn];

// ------------------------------------------------------------------------------------------------------------------------



void solve()
{
    cin >> n >> K;
    FOR(i, 1, n) cin >> a[i];

    FOR(i, 1, n) dp_cur[i] = 1e18;

    FOR(ik, 1, K)
    {
        FOR(i, 0, n)
        {
            dp_before[i] = dp_cur[i];
            dp_cur[i] = 1e18;
        }

        vector<int> st;
        FOR(i, 1, n)
        {
            minF[i] = dp_before[i - 1];
            while (st.size() && a[st.back()] <= a[i])
            {
                minF[i] = min(minF[i], minF[st.back()]);
                st.pop_back();
            }

            if (st.size()) dp_cur[i] = dp_cur[st.back()];
            dp_cur[i] = min(dp_cur[i], minF[i] + a[i]);

            st.push_back(i);
        }
    }

    cout << dp_cur[n];
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

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

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