oj.uz

Submission #235790

# Submission time Handle Problem Language Result Execution time Memory
235790 2020-05-29T21:21:04 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
25 / 100
 114 ms 36352 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;
  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);
  }
  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 21 ms 36096 KB Output is correct
2 Correct 22 ms 36096 KB Output is correct
3 Correct 23 ms 36096 KB Output is correct
4 Incorrect 22 ms 36096 KB Output isn't correct
5 Incorrect 25 ms 36224 KB Output isn't correct
6 Correct 23 ms 36224 KB Output is correct
7 Incorrect 22 ms 36224 KB Output isn't correct
8 Incorrect 24 ms 36224 KB Output isn't correct
9 Incorrect 26 ms 36224 KB Output isn't correct
10 Incorrect 27 ms 36224 KB Output isn't correct
11 Incorrect 26 ms 36224 KB Output isn't correct
12 Incorrect 37 ms 36352 KB Output isn't correct
13 Incorrect 42 ms 36216 KB Output isn't correct
14 Incorrect 29 ms 36224 KB Output isn't correct
15 Incorrect 46 ms 36224 KB Output isn't correct
16 Incorrect 25 ms 36224 KB Output isn't correct
17 Incorrect 33 ms 36224 KB Output isn't correct
18 Incorrect 76 ms 36224 KB Output isn't correct
19 Correct 114 ms 36344 KB Output is correct
20 Incorrect 114 ms 36224 KB Output isn't correct