Submission #346493

#	Time	Username	Problem	Language	Result	Execution time	Memory
346493		MilosMilutinovic	Raisins (IOI09_raisins)	C++14	100 / 100	2053 ms	58800 KiB

raisins

/**
 *  author: milos
 *  created: 10.01.2021 02:07:32
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 51;

int n, m;
vector<vector<int>> a(N, vector<int>(N));
vector<vector<vector<vector<long long>>>> dp(N, vector<vector<vector<long long>>>(N, vector<vector<long long>>(N, vector<long long>(N, 0))));

long long Calc(int x1, int y1, int x2, int y2) {
  if (x1 == x2 && y1 == y2) {
    return 0LL;
  }
  if (dp[x1][y1][x2][y2] != 0) {
    return dp[x1][y1][x2][y2]; 
  }            
  //cout << x1 << " " << y1 << " " << x2 << " " << y2 << '\n';  
  long long ans = 1e18, sum = 0;
  for (int i = x1; i <= x2; i++) {
    for (int j = y1; j <= y2; j++) {
      sum += a[i][j];
    }
  }
  for (int i = x1 + 1; i <= x2; i++) {
    ans = min(ans, Calc(x1, y1, i - 1, y2) + Calc(i, y1, x2, y2)); 
  }
  for (int i = y1 + 1; i <= y2; i++) {
    ans = min(ans, Calc(x1, y1, x2, i - 1) + Calc(x1, i, x2, y2)); 
  }
  ans += sum;
  dp[x1][y1][x2][y2] = ans;
  return ans;
}
    
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }                     
  cout << Calc(0, 0, n - 1, m - 1) << '\n';
  return 0;
}

• Subtask 1: 100 / 100