oj.uz

Submission #445795

# Submission time Handle Problem Language Result Execution time Memory
445795 2021-07-19T15:15:22 Z dxz05 K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -