제출 #844795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844795		asdfgrace	Raisins (IOI09_raisins)	C++17	100 / 100	77 ms	36440 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 55;
int dp[N][N][N][N];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
    }
  }
  vector<vector<int>> psum = a;
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j < m; ++j) {
      psum[i][j] += psum[i][j - 1];
    }
  }
  for (int j = 0; j < m; ++j) {
    for (int i = 1; i < n; ++i) {
      psum[i][j] += psum[i - 1][j];
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  for (int il = n - 1; il >= 0; --il) {
    for (int ir = il; ir < n; ++ir) {
      for (int jl = m - 1; jl >= 0; --jl) {
        for (int jr = jl; jr < m; ++jr) {
          int sum = (il && jl ? psum[il - 1][jl - 1] : 0) + psum[ir][jr]
            - (il ? psum[il - 1][jr] : 0) - (jl ? psum[ir][jl - 1] : 0);
          if (il == ir && jl == jr) {
            dp[il][ir][jl][jr] = 0;
            continue;
          }
          for (int im = il; im < ir; ++im) {
            dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr],
              dp[il][im][jl][jr] + dp[im + 1][ir][jl][jr] + sum);
          }
          for (int jm = jl; jm < jr; ++jm) {
            dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr],
              dp[il][ir][jl][jm] + dp[il][ir][jm + 1][jr] + sum);
          }
        }
      }
    }
  }
  cout << dp[0][n - 1][0][m - 1] << '\n';
}

• Subtask 1: 100 / 100