Submission #1162840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162840		lopkus	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	121 ms	3144 KiB

blocks

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int n, k;

int main() {
    scanf("%d %d", &n, &k);
    vector<int> a(n + 5);
    vector<vector<ll>> dp(2, vector<ll>(n + 5));
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) dp[1][i] = max(dp[1][i - 1], (ll) a[i]);
    for (int i = 2; i <= k; i++) {
        for (int j = 0; j <= n; j++) dp[i & 1][j] = 0;
        stack<pii> st;
        for (int j = i; j <= n; j++) {
            ll cmn = dp[!(i & 1)][j - 1];
            while (!st.empty() && a[st.top().first] <= a[j]) {
                cmn = min(cmn, st.top().second);
                st.pop();
            }
            dp[i & 1][j] = cmn + a[j];
            if (!st.empty()) dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1][st.top().first]);
            st.emplace(j, cmn);
        }
        for (int j = 0; j < i; j++) dp[i & 1][j] = 1e18;
    }
    printf("%lld", dp[k & 1][n]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
blocks.cpp:13:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

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