oj.uz

Submission #509926

# Submission time Handle Problem Language Result Execution time Memory
509926 2022-01-14T12:15:31 Z 600Mihnea Raisins (IOI09_raisins) C++17
100 / 100
 582 ms 83020 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 50 + 7;
const int INF = (int) 1e18;
int n, m, dp[N][N][N][N], p[N][N];

int getsum(int r1, int c1, int r2, int c2) {
  return p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1];
}

int getdp(int r1, int c1, int r2, int c2) {
  assert(r1 <= r2 && c1 <= c2);
  if (r1 == r2 && c1 == c2) return 0;
  if (dp[r1][c1][r2][c2] != INF) return dp[r1][c1][r2][c2];

  int &sol = dp[r1][c1][r2][c2];
  for (int r = r1; r <= r2 - 1; r++) {
    sol = min(sol, getdp(r1, c1, r, c2) + getdp(r + 1, c1, r2, c2));
  }

  for (int c = c1; c <= c2 - 1; c++) {
    sol = min(sol, getdp(r1, c1, r2, c) + getdp(r1, c + 1, r2, c2));
  }


  sol += getsum(r1, c1, r2, c2);
  return sol;
}

signed main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int c = 0;
    for (int j = 1; j <= m; j++) {
      int x;
      cin >> x;
      c += x;
      p[i][j] = p[i - 1][j] + c;
    }
  }

  for (int a = 0; a < N; a++) for (int b = 0; b < N; b++) for (int c = 0; c < N; c++) for (int d = 0; d < N; d++) dp[a][b][c][d] = INF;




  cout << getdp(1, 1, n, m) << "\n";

  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 82816 KB Output is correct
2 Correct 40 ms 82828 KB Output is correct
3 Correct 39 ms 82808 KB Output is correct
4 Correct 35 ms 82864 KB Output is correct
5 Correct 36 ms 82884 KB Output is correct
6 Correct 36 ms 82836 KB Output is correct
7 Correct 36 ms 82868 KB Output is correct
8 Correct 40 ms 82884 KB Output is correct
9 Correct 47 ms 82884 KB Output is correct
10 Correct 50 ms 82852 KB Output is correct
11 Correct 49 ms 82884 KB Output is correct
12 Correct 87 ms 82888 KB Output is correct
13 Correct 119 ms 82928 KB Output is correct
14 Correct 57 ms 82920 KB Output is correct
15 Correct 140 ms 82904 KB Output is correct
16 Correct 44 ms 82832 KB Output is correct
17 Correct 75 ms 82936 KB Output is correct
18 Correct 314 ms 82936 KB Output is correct
19 Correct 519 ms 82980 KB Output is correct
20 Correct 582 ms 83020 KB Output is correct