Submission #346472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346472	2021-01-09T20:58:56 Z	dgq	Raisins (IOI09_raisins)	C++17	100 / 100	1006 ms	13676 KB

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

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.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	3180 KB	Output is correct
11	Correct	26 ms	2412 KB	Output is correct
12	Correct	95 ms	5740 KB	Output is correct
13	Correct	167 ms	6764 KB	Output is correct
14	Correct	44 ms	2668 KB	Output is correct
15	Correct	205 ms	7660 KB	Output is correct
16	Correct	24 ms	5100 KB	Output is correct
17	Correct	87 ms	7660 KB	Output is correct
18	Correct	557 ms	12028 KB	Output is correct
19	Correct	857 ms	12576 KB	Output is correct
20	Correct	1006 ms	13676 KB	Output is correct