oj.uz

Submission #235791

# Submission time Handle Problem Language Result Execution time Memory
235791 2020-05-29T21:21:42 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
25 / 100
 114 ms 36228 KB 
/**
 *  author: Duarte Nobrega
 *  created: 29.05.2020    
**/
 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 50 + 5;

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 <= (x1 + 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;
      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 <= (y1 + 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;
      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
25.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 36224 KB Output is correct
4 Incorrect 24 ms 36096 KB Output isn't correct
5 Incorrect 22 ms 36224 KB Output isn't correct
6 Correct 25 ms 36224 KB Output is correct
7 Incorrect 22 ms 36096 KB Output isn't correct
8 Incorrect 25 ms 36224 KB Output isn't correct
9 Incorrect 26 ms 36224 KB Output isn't correct
10 Incorrect 26 ms 36224 KB Output isn't correct
11 Incorrect 26 ms 36224 KB Output isn't correct
12 Incorrect 34 ms 36224 KB Output isn't correct
13 Incorrect 42 ms 36224 KB Output isn't correct
14 Incorrect 30 ms 36216 KB Output isn't correct
15 Incorrect 45 ms 36224 KB Output isn't correct
16 Incorrect 26 ms 36224 KB Output isn't correct
17 Incorrect 33 ms 36224 KB Output isn't correct
18 Incorrect 72 ms 36224 KB Output isn't correct
19 Correct 109 ms 36228 KB Output is correct
20 Incorrect 114 ms 36224 KB Output isn't correct