Submission #743106

#	Time	Username	Problem	Language	Result	Execution time	Memory
743106		sleepntsheep	Raisins (IOI09_raisins)	C++17	100 / 100	753 ms	36144 KiB

raisins

#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 (stderr)

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 / 100