Submission #1077471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077471		meowww	K blocks (IZhO14_blocks)	C++17	53 / 100	1029 ms	4260 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define int long long
#define vi vector <int>
#define vb vector <bool>
#define vvi vector <vector <int>>
#define fi first
#define se second
#define pii pair <int, int>
#define all(x) x.begin(), x.end()

int solution(const vi& A, int K) {
    int N = A.size();
    vvi dp(K + 1, vi(N + 1, INT_MAX));
    
    vi pre(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        pre[i] = max(pre[i-1], A[i-1]);
    }

    for (int i = 1; i <= N; i++) {
        dp[1][i] = pre[i];
    }

    for (int k = 2; k <= K; k++) {
        for (int i = k; i <= N; i++) {
            int cur = 0;
            for (int j = i; j >= k; j--) {
                cur = max(cur, A[j-1]);
                dp[k][i] = min(dp[k][i], dp[k-1][j-1] + cur);
            }
        }
    }

    return dp[K][N];
}

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
    int N, K;
    cin >> N >> K;

    vi A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << solution(A, K) << endl;

    return 0;
}

Compilation message (stderr)

blocks.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~

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