oj.uz

Submission #235786

# Submission time Handle Problem Language Result Execution time Memory
235786 2020-05-29T21:14:05 Z Haunted_Cpp Raisins (IOI09_raisins) C++17
10 / 100
 54 ms 72064 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];
i64 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;

i64 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;
  i64 &res = dp[x1][y1][x2][y2];
  if (~res) return res;
  res = 1e18;
  for (int i = x1; i <= 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;
    i64 cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
    i64 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 / 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;
    i64 cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2);
    i64 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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71936 KB Output is correct
2 Correct 37 ms 71928 KB Output is correct
3 Incorrect 39 ms 71928 KB Output isn't correct
4 Incorrect 39 ms 71928 KB Output isn't correct
5 Incorrect 39 ms 71928 KB Output isn't correct
6 Incorrect 38 ms 71928 KB Output isn't correct
7 Incorrect 39 ms 71928 KB Output isn't correct
8 Incorrect 39 ms 71928 KB Output isn't correct
9 Incorrect 38 ms 72056 KB Output isn't correct
10 Incorrect 38 ms 72056 KB Output isn't correct
11 Incorrect 38 ms 72056 KB Output isn't correct
12 Incorrect 40 ms 72056 KB Output isn't correct
13 Incorrect 42 ms 71928 KB Output isn't correct
14 Incorrect 38 ms 71928 KB Output isn't correct
15 Incorrect 43 ms 72056 KB Output isn't correct
16 Incorrect 38 ms 72056 KB Output isn't correct
17 Incorrect 40 ms 72064 KB Output isn't correct
18 Incorrect 47 ms 72012 KB Output isn't correct
19 Incorrect 52 ms 72064 KB Output isn't correct
20 Incorrect 54 ms 71928 KB Output isn't correct