Submission #235786

#	Time	Username	Problem	Language	Result	Execution time	Memory
235786		Haunted_Cpp	Raisins (IOI09_raisins)	C++17	10 / 100	54 ms	72064 KiB

raisins

/**
 *  author: Duarte Nobrega
 *  created: 29.05.2020    
**/
 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 50 + 5;

typedef long long i64;

int g [N][N], s [N][N];
i64 dp [N][N][N][N];

int range_query (int x1, int y1, int x2, int y2) {
  return s[x2][y2] - (x1 - 1 >= 0 ? s[x1 - 1][y2] : 0) - (y1 - 1 >= 0 ? s[x2][y1 - 1] : 0) + (x1 - 1 >= 0 && y1 - 1 >= 0 ? s[x1 - 1][y1 - 1] : 0);
}

int r, c;

i64 solve (int x1, int y1, int x2, int y2) {
  if (x1 > x2) return 0;
  if (y1 > y2) return 0;
  if (x1 == x2 && y1 == y2) return 0;
  i64 &res = dp[x1][y1][x2][y2];
  if (~res) return res;
  res = 1e18;
  for (int i = x1; i <= x2 / 2; i++) {
    int cima_x1 = x1;
    int cima_y1 = y1;
    int cima_x2 = i;
    int cima_y2 = y2;
    int baixo_x1 = i + 1;
    int baixo_y1 = y1;
    int baixo_x2 = x2;
    int baixo_y2 = y2;
    i64 cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
    i64 other = solve (cima_x1, cima_y1, cima_x2, cima_y2) + solve (baixo_x1, baixo_y1, baixo_x2, baixo_y2);  
    res = min (res, cost_of_split + other);
  }
  for (int i = y1; i <= y2 / 2; i++) {
    int cima_x1 = x1;
    int cima_y1 = y1;
    int cima_x2 = x2;
    int cima_y2 = i;
    int baixo_x1 = x1;
    int baixo_y1 = i + 1;
    int baixo_x2 = x2;
    int baixo_y2 = y2;
    i64 cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
    i64 other = solve (cima_x1, cima_y1, cima_x2, cima_y2) + solve (baixo_x1, baixo_y1, baixo_x2, baixo_y2);  
    res = min (res, cost_of_split + other);
  }
  return res;
}


int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> r >> c;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> g[i][j];
    }
  }
  s[0][0] = g[0][0];
  for (int i = 1; i < c; i++) s[0][i] = s[0][i - 1] + g[0][i];
  for (int i = 1; i < r; i++) s[i][0] = s[i - 1][0] + g[i][0];
  for (int i = 1; i < r; i++) {
    for (int j = 1; j < c; j++) {
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];
    }
  }
  memset (dp, -1, sizeof(dp));
  cout << solve (0, 0, r - 1, c - 1) << '\n'; 
  return 0;
}

• Subtask 1: 10 / 100