Submission #509926

#	Time	Username	Problem	Language	Result	Execution time	Memory
509926		600Mihnea	Raisins (IOI09_raisins)	C++17	100 / 100	582 ms	83020 KiB

raisins

#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 / 100