Submission #1078386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078386	2024-08-27T16:25:14 Z	sqrteipi	Raisins (IOI09_raisins)	C++14	100 / 100	171 ms	26452 KB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
int diff[51][51], dp[51][51][51][51];

#define query(lx, rx, ly, ry) diff[rx][ry] - diff[lx-1][ry] - diff[rx][ly-1] + diff[lx-1][ly-1]
int solve(int lx, int rx, int ly, int ry) {
  if (dp[lx][rx][ly][ry]) return dp[lx][rx][ly][ry];
  if (lx==rx&&ly==ry) return 0;
  int bst = 1e18;
  for (int i=lx; i<rx; i++) {
    int cur = query(lx, rx, ly, ry) + solve(lx, i, ly, ry) + solve(i+1, rx, ly, ry);
    bst = min(bst, cur);
  }
  for (int i=ly; i<ry; i++) {
    int cur = query(lx, rx, ly, ry) + solve(lx, rx, ly, i) + solve(lx, rx, i+1, ry);
    bst = min(bst, cur);
  }
  dp[lx][rx][ly][ry] = bst;
  return bst;
}

int32_t main() {
  int n, m;
  cin >> n >> m;
  for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
    cin >> diff[i][j];
    diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
  }
  cout << solve(1, n, 1, m);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	0 ms	604 KB	Output is correct
6	Correct	1 ms	860 KB	Output is correct
7	Correct	1 ms	1112 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	6 ms	4188 KB	Output is correct
10	Correct	8 ms	4952 KB	Output is correct
11	Correct	7 ms	3508 KB	Output is correct
12	Correct	21 ms	9076 KB	Output is correct
13	Correct	34 ms	11536 KB	Output is correct
14	Correct	15 ms	4444 KB	Output is correct
15	Correct	43 ms	13180 KB	Output is correct
16	Correct	7 ms	6748 KB	Output is correct
17	Correct	20 ms	11416 KB	Output is correct
18	Correct	119 ms	23212 KB	Output is correct
19	Correct	154 ms	24588 KB	Output is correct
20	Correct	171 ms	26452 KB	Output is correct