Submission #343124

#	Time	Username	Problem	Language	Result	Execution time	Memory
343124		Sprdalo	K blocks (IZhO14_blocks)	C++17	53 / 100	142 ms	262148 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;


signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, k;
    cin >> n >> k;

    vi a(n+1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<vi> m(n+1, vi(n+1,0));
    for (int i = 1; i <= n; ++i){
        m[i][i] = a[i];
        for (int j = i+1; j <= n; ++j){
            m[i][j] = max(m[i][j-1], a[j]);
        }
    }

    vector<vi> dp(k+1,vi(n+1,INT32_MAX));

    for (int i = 1; i <= n; ++i){
        dp[1][i] = m[1][i];
    }

    for (int i = 2; i <= k; ++i){
        for (int j = 1; j <= n; ++j){
            for (int t = 1; t < j; ++t){
                dp[i][j] = min(dp[i-1][t] + m[t+1][j], dp[i][j]);
            }
        }
    }

    cout << dp[k][n] << '\n';
}

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