제출 #1257726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257726		kunzaZa183	건포도 (IOI09_raisins)	C++20	100 / 100	187 ms	49380 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mn = 50;
int dp[mn][mn][mn][mn];
int vvi[mn + 1][mn + 1] = {}, qsum[mn + 1][mn + 1] = {};
int ans(int x1, int y1, int x2, int y2) {
  if (x1 == x2 && y1 == y2) {
    return 0;
  }

  if (dp[x1][y1][x2][y2] != -1) {
    return dp[x1][y1][x2][y2];
  }

  int cur =
      qsum[x2 + 1][y2 + 1] - qsum[x2 + 1][y1] - qsum[x1][y2 + 1] + qsum[x1][y1];
  dp[x1][y1][x2][y2] = LLONG_MAX;
  if (x1 != x2) {
    for (int i = x1; i < x2; i++) {
      dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur + ans(x1, y1, i, y2) +
                                                       ans(i + 1, y1, x2, y2));
    }
  }
  if (y1 != y2) {
    for (int i = y1; i < y2; i++) {
      dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur + ans(x1, y1, x2, i) +
                                                       ans(x1, i + 1, x2, y2));
    }
  }

  // cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << cur << " "
  //      << dp[x1][y1][x2][y2] << "\n";

  return dp[x1][y1][x2][y2];
}
signed main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      cin >> vvi[i][j];
      qsum[i][j] +=
          qsum[i - 1][j] + qsum[i][j - 1] - qsum[i - 1][j - 1] + vvi[i][j];
    }
  memset(dp, -1, sizeof dp);
  cout << ans(0, 0, n - 1, m - 1) << "\n";
}

• Subtask 1: 100 / 100