Submission #758730

#	Time	Username	Problem	Language	Result	Execution time	Memory
758730		JANCARAPAN	Raisins (IOI09_raisins)	C++17	100 / 100	174 ms	58668 KiB

raisins

#include <bits/stdc++.h>
using namespace std;  
#define ll long long
#define fi first
#define se second
#define sz(a) (long long) a.size()
#define endl '\n'

const long long INF = 1e18, MOD = 1e9+7; 

void test_case() {
  int n, m;
  cin >> n >> m;
  vector pref(n + 1, vector<int>(m + 1));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int x;
      cin >> x;
      pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + x;
    }
  }
  vector dp(n + 1, vector(m + 1, vector(n + 1, vector<ll>(m + 1, INF)))); // dp[py][px][qy][qx] P = (px, py), Q = (qx, qy)
  
  for (int py = 1; py <= n; py++) {
    for (int px = 1; px <= m; px++) {
      dp[py][px][py - 1][px - 1] = 0;
    }
  }
  
  auto range = [&](int py, int px, int qy, int qx) {
    return pref[py][px] - pref[py][qx] - pref[qy][px] + pref[qy][qx];
  };
  
  for (int py = 1; py <= n; py++) {
    for (int px = 1; px <= m; px++) {
      for (int qy = py - 1; qy >= 0; qy--) {
        for (int qx = px - 1; qx >= 0; qx--) {
          if (qy == py - 1 and qx == px - 1) continue;
          
          // now i try to make some horizontal cut
          for (int cuty = py - 1; cuty > qy; cuty--) {
            dp[py][px][qy][qx] = min(dp[py][px][qy][qx], dp[py][px][cuty][qx] + dp[cuty][px][qy][qx]);
          }
          // now i try to make some vertical cut
          for (int cutx = px - 1; cutx > qx; cutx--) {
            dp[py][px][qy][qx] = min(dp[py][px][qy][qx], dp[py][px][qy][cutx] + dp[py][cutx][qy][qx]);
          }
          dp[py][px][qy][qx] += range(py, px, qy, qx);
        }
      }
    }
  }
  cout << dp[n][m][0][0] << endl;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    test_case();
  }
  return 0;
}

• Subtask 1: 100 / 100