oj.uz

Submission #235792

# Submission time Handle Problem Language Result Execution time Memory
235792 2020-05-29T21:22:45 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
100 / 100
 940 ms 36344 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 <= 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);
  }
  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 24 ms 36116 KB Output is correct
3 Correct 23 ms 36096 KB Output is correct
4 Correct 24 ms 36224 KB Output is correct
5 Correct 23 ms 36224 KB Output is correct
6 Correct 25 ms 36096 KB Output is correct
7 Correct 23 ms 36224 KB Output is correct
8 Correct 34 ms 36212 KB Output is correct
9 Correct 47 ms 36224 KB Output is correct
10 Correct 51 ms 36224 KB Output is correct
11 Correct 47 ms 36224 KB Output is correct
12 Correct 116 ms 36236 KB Output is correct
13 Correct 179 ms 36344 KB Output is correct
14 Correct 76 ms 36344 KB Output is correct
15 Correct 234 ms 36344 KB Output is correct
16 Correct 39 ms 36224 KB Output is correct
17 Correct 99 ms 36224 KB Output is correct
18 Correct 542 ms 36320 KB Output is correct
19 Correct 872 ms 36344 KB Output is correct
20 Correct 940 ms 36224 KB Output is correct