oj.uz

Submission #235794

# Submission time Handle Problem Language Result Execution time Memory
235794 2020-05-29T21:29:18 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
100 / 100
 706 ms 36428 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 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 other = solve (x1, y1, i, y2) + solve (i + 1, y1, x2, y2);  
    res = min (res, other);
  }
  for (int i = y1; i <= y2; i++) {
    int other = solve (x1, y1, x2, i) + solve (x1, i + 1, x2, y2);  
    res = min (res, other);
  }
  return res += 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 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 23 ms 36096 KB Output is correct
2 Correct 23 ms 36224 KB Output is correct
3 Correct 22 ms 36096 KB Output is correct
4 Correct 23 ms 36096 KB Output is correct
5 Correct 27 ms 36216 KB Output is correct
6 Correct 23 ms 36096 KB Output is correct
7 Correct 23 ms 36224 KB Output is correct
8 Correct 30 ms 36224 KB Output is correct
9 Correct 40 ms 36224 KB Output is correct
10 Correct 44 ms 36352 KB Output is correct
11 Correct 41 ms 36224 KB Output is correct
12 Correct 89 ms 36224 KB Output is correct
13 Correct 137 ms 36344 KB Output is correct
14 Correct 54 ms 36224 KB Output is correct
15 Correct 160 ms 36344 KB Output is correct
16 Correct 33 ms 36224 KB Output is correct
17 Correct 85 ms 36132 KB Output is correct
18 Correct 402 ms 36224 KB Output is correct
19 Correct 605 ms 36428 KB Output is correct
20 Correct 706 ms 36344 KB Output is correct