Submission #346850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346850	2021-01-11T09:20:33 Z	BlancaHM	Raisins (IOI09_raisins)	C++14	100 / 100	1016 ms	13556 KB

raisins

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

using namespace std;

const int N = 51;  // el máximo valor, más 1 para operar en el rango 1..50.
const int M = 51;
vector<vector<int>> ps_v;  // 2D prefix sums de los valores (núm. de raisins).

// Retorna el mínimo coste de partir una tableta rectangular de dimensiones
// horizontales x..X y verticales y..Y
int f(int x, int X, int y, int Y) {
  static int dp[N][M][N][M];  // dp se inicializará con ceros al ser static
  if (x + 1 == X && y + 1 == Y) return 0;  // caso base
  if (dp[x][X][y][Y]) return dp[x][X][y][Y];
  int minimo = INT_MAX;
  // Calculemos, de entre todos los cortes verticales y horizontales posibles,
  // aquel de coste mínimo.
  // Cortes horizontales
  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 */);
  }
  // Cortes verticales
  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 */);
  }
  // Combinamos el resultado mínimo obtenido de los subproblemas con el coste
  // del problema actual, utilizando 2D prefix sums.
  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;
  cin >> 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++) {
      cin >> ps_v[i][j];
    }
  }
  // Cálculo de las 2D prefix sums
  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];
    }
  }
  cout << f(0, n, 0, m) << '\n';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	620 KB	Output is correct
7	Correct	2 ms	1004 KB	Output is correct
8	Correct	12 ms	1772 KB	Output is correct
9	Correct	21 ms	2796 KB	Output is correct
10	Correct	31 ms	3308 KB	Output is correct
11	Correct	26 ms	2412 KB	Output is correct
12	Correct	101 ms	5652 KB	Output is correct
13	Correct	167 ms	6764 KB	Output is correct
14	Correct	42 ms	2668 KB	Output is correct
15	Correct	209 ms	7532 KB	Output is correct
16	Correct	23 ms	5100 KB	Output is correct
17	Correct	86 ms	7660 KB	Output is correct
18	Correct	589 ms	11884 KB	Output is correct
19	Correct	856 ms	12464 KB	Output is correct
20	Correct	1016 ms	13556 KB	Output is correct