Submission #445795

#	Time	Username	Problem	Language	Result	Execution time	Memory
445795		dxz05	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	204 KiB

blocks

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define SZ(x) (int)(x).size()

const int MAXN = 1e6 + 3e2;

int a[MAXN];
int dp[111][111];

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr); cout.tie(nullptr);

    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++){
        scanf("%d", a + i);
    }

    for (int i = 1; i <= n; i++){
        fill(dp[i] + 1, dp[i] + k + 1, 1e9);
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            int mx = 0;
            for (int l = i; l >= j; l--){
                mx = max(mx, a[l]);
                dp[i][j] = min(dp[i][j], dp[l - 1][j - 1] + mx);
            }
            //cout << dp[i][j] << ' ';
        }
        //cout << endl;
    }

    printf("%d", dp[n][k]);

    return 0;
}

Compilation message (stderr)

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

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