oj.uz

Submission #235789

# Submission time Handle Problem Language Result Execution time Memory
235789 2020-05-29T21:18:30 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
100 / 100
 1012 ms 36344 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];
int 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;

int 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;
  int &res = dp[x1][y1][x2][y2];
  if (~res) return res;
  res = 1e9;
  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;
      int cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
      int 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;
      int cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
      int 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 22 ms 36096 KB Output is correct
2 Correct 22 ms 36096 KB Output is correct
3 Correct 22 ms 36096 KB Output is correct
4 Correct 21 ms 36224 KB Output is correct
5 Correct 23 ms 36224 KB Output is correct
6 Correct 22 ms 36096 KB Output is correct
7 Correct 21 ms 36224 KB Output is correct
8 Correct 32 ms 36096 KB Output is correct
9 Correct 40 ms 36224 KB Output is correct
10 Correct 56 ms 36224 KB Output is correct
11 Correct 48 ms 36224 KB Output is correct
12 Correct 109 ms 36224 KB Output is correct
13 Correct 177 ms 36344 KB Output is correct
14 Correct 68 ms 36344 KB Output is correct
15 Correct 255 ms 36224 KB Output is correct
16 Correct 36 ms 36224 KB Output is correct
17 Correct 116 ms 36344 KB Output is correct
18 Correct 504 ms 36224 KB Output is correct
19 Correct 824 ms 36344 KB Output is correct
20 Correct 1012 ms 36344 KB Output is correct