oj.uz

Submission #743106

# Submission time Handle Problem Language Result Execution time Memory
743106 2023-05-17T08:06:38 Z sleepntsheep Raisins (IOI09_raisins) C++17
100 / 100
 753 ms 36144 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 55
int n, m, a[N][N], b[N][N], dp[N][N][N][N];

int O(int i, int j, int k, int l)
{
    int &d = dp[i][j][k][l];
    if (d + 1) return d;
    d = 1e9;
    for (int o = i; o < k; o++)
        d = min(d, O(i, j, o, l) + O(o+1, j, k, l) + b[k][l] - b[i-1][l] - b[k][j-1] + b[i-1][j-1]);
    for (int o = j; o < l; o++)
        d = min(d, O(i, j, k, o) + O(i, o+1, k, l) + b[k][l] - b[i-1][l] - b[k][j-1] + b[i-1][j-1]);
    return d;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        scanf("%d", &a[i][j]), b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];

    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j][i][j] = 0;

    printf("%d\n", O(1, 1, n, m));


    return 0;
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36052 KB Output is correct
2 Correct 15 ms 36000 KB Output is correct
3 Correct 15 ms 36052 KB Output is correct
4 Correct 14 ms 36020 KB Output is correct
5 Correct 14 ms 36052 KB Output is correct
6 Correct 15 ms 36052 KB Output is correct
7 Correct 16 ms 36016 KB Output is correct
8 Correct 24 ms 36056 KB Output is correct
9 Correct 29 ms 36052 KB Output is correct
10 Correct 39 ms 36112 KB Output is correct
11 Correct 36 ms 36112 KB Output is correct
12 Correct 82 ms 36052 KB Output is correct
13 Correct 131 ms 36128 KB Output is correct
14 Correct 49 ms 36120 KB Output is correct
15 Correct 162 ms 36052 KB Output is correct
16 Correct 28 ms 36104 KB Output is correct
17 Correct 74 ms 36124 KB Output is correct
18 Correct 388 ms 36144 KB Output is correct
19 Correct 651 ms 36136 KB Output is correct
20 Correct 753 ms 36112 KB Output is correct