Submission #346472

#	Time	Username	Problem	Language	Result	Execution time	Memory
346472		dgq	Raisins (IOI09_raisins)	C++17	100 / 100	1006 ms	13676 KiB

raisins

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

const int N = 51;
const int M = 51;
vector<vector<int>> ps_v;

int f(int x, int X, int y, int Y) {
  static int dp[N][M][N][M];  
  if (x + 1 == X && y + 1 == Y) return 0;  
  if (dp[x][X][y][Y]) return dp[x][X][y][Y];
  int minimo = INT_MAX;
  for (int i = x + 1; i < X; i++) {
    minimo = min(minimo,
        f(x, i, y, Y) /* cacho superior */ + f(i, X, y, Y) /* cacho inferior */);
  }
  for (int i = y + 1; i < Y; i++) {
    minimo = min(minimo,
        f(x, X, y, i) /* cacho izquierdo*/ + f(x, X, i, Y) /* cacho derecho */);
  }
  return dp[x][X][y][Y] = minimo + ps_v[X][Y] - ps_v[x][Y] - ps_v[X][y] + ps_v[x][y];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  ps_v = vector<vector<int>>(n + 1, vector<int>(m + 1));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &ps_v[i][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      ps_v[i][j] += ps_v[i - 1][j] + ps_v[i][j - 1] - ps_v[i - 1][j - 1];
    }
  }
  printf("%d\n", f(0, n, 0, m));
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
raisins.cpp:33:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |       scanf("%d", &ps_v[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100