Submission #346853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346853	2021-01-11T09:24:49 Z	BlancaHM	Raisins (IOI09_raisins)	C++14	100 / 100	1479 ms	33388 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, vector<vector<vector<vector<int>>>> & dp) {
  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, dp) /* cacho superior */ +
                             f(i, X, y, Y, dp) /* cacho inferior */);
  }
  // Cortes verticales
  for (int i = y + 1; i < Y; i++) {
    minimo = min(minimo, f(x, X, y, i, dp) /* cacho izquierdo*/ +
                             f(x, X, i, Y, dp) /* 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));
  vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>>(M, vector<vector<int>>(N, vector<int>(M, 0))));
  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, dp) << '\n';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	33260 KB	Output is correct
2	Correct	26 ms	33260 KB	Output is correct
3	Correct	25 ms	33260 KB	Output is correct
4	Correct	25 ms	33260 KB	Output is correct
5	Correct	26 ms	33260 KB	Output is correct
6	Correct	26 ms	33260 KB	Output is correct
7	Correct	26 ms	33260 KB	Output is correct
8	Correct	38 ms	33260 KB	Output is correct
9	Correct	51 ms	33260 KB	Output is correct
10	Correct	63 ms	33388 KB	Output is correct
11	Correct	61 ms	33260 KB	Output is correct
12	Correct	156 ms	33260 KB	Output is correct
13	Correct	258 ms	33260 KB	Output is correct
14	Correct	74 ms	33260 KB	Output is correct
15	Correct	316 ms	33260 KB	Output is correct
16	Correct	50 ms	33260 KB	Output is correct
17	Correct	146 ms	33260 KB	Output is correct
18	Correct	803 ms	33388 KB	Output is correct
19	Correct	1255 ms	33300 KB	Output is correct
20	Correct	1479 ms	33388 KB	Output is correct