oj.uz

Submission #235787

# Submission time Handle Problem Language Result Execution time Memory
235787 2020-05-29T21:17:26 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
100 / 100
 1070 ms 72064 KB 
/**
 *  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;
  if (x1 != x2) {
    for (int i = x1; i <= x2; 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);
    }
  }
  if (y1 != y2) {
    for (int i = y1; i <= y2; 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 71936 KB Output is correct
2 Correct 39 ms 71928 KB Output is correct
3 Correct 38 ms 71928 KB Output is correct
4 Correct 38 ms 71928 KB Output is correct
5 Correct 37 ms 71928 KB Output is correct
6 Correct 38 ms 71936 KB Output is correct
7 Correct 39 ms 71936 KB Output is correct
8 Correct 49 ms 71928 KB Output is correct
9 Correct 59 ms 72064 KB Output is correct
10 Correct 77 ms 71980 KB Output is correct
11 Correct 63 ms 71928 KB Output is correct
12 Correct 134 ms 71936 KB Output is correct
13 Correct 204 ms 71928 KB Output is correct
14 Correct 82 ms 71928 KB Output is correct
15 Correct 255 ms 72056 KB Output is correct
16 Correct 55 ms 72056 KB Output is correct
17 Correct 118 ms 72056 KB Output is correct
18 Correct 575 ms 71932 KB Output is correct
19 Correct 920 ms 72056 KB Output is correct
20 Correct 1070 ms 72056 KB Output is correct