Submission #1078386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078386		sqrteipi	Raisins (IOI09_raisins)	C++14	100 / 100	171 ms	26452 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
int diff[51][51], dp[51][51][51][51];

#define query(lx, rx, ly, ry) diff[rx][ry] - diff[lx-1][ry] - diff[rx][ly-1] + diff[lx-1][ly-1]
int solve(int lx, int rx, int ly, int ry) {
  if (dp[lx][rx][ly][ry]) return dp[lx][rx][ly][ry];
  if (lx==rx&&ly==ry) return 0;
  int bst = 1e18;
  for (int i=lx; i<rx; i++) {
    int cur = query(lx, rx, ly, ry) + solve(lx, i, ly, ry) + solve(i+1, rx, ly, ry);
    bst = min(bst, cur);
  }
  for (int i=ly; i<ry; i++) {
    int cur = query(lx, rx, ly, ry) + solve(lx, rx, ly, i) + solve(lx, rx, i+1, ry);
    bst = min(bst, cur);
  }
  dp[lx][rx][ly][ry] = bst;
  return bst;
}

int32_t main() {
  int n, m;
  cin >> n >> m;
  for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
    cin >> diff[i][j];
    diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
  }
  cout << solve(1, n, 1, m);
}

• Subtask 1: 100 / 100