Submission #298501

# Submission time Handle Problem Language Result Execution time Memory
298501 2020-09-13T03:27:43 Z deodeo Raisins (IOI09_raisins) C++14
45 / 100
1012 ms 25080 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
typedef pair<pair<int, int>, int> piii;

const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;

template <class T, class C = less<T>>
using ordered_set = tree<T, null_type, C, rb_tree_tag, tree_order_statistics_node_update>;

int grid[50][50], dp[50][50][50][50];

int solve(int r1, int c1, int r2, int c2) {
	if (r1 == r2 && c1 == c2) return 0;
	if (dp[r1][c1][r2][c2] != -1) return dp[r1][c1][r2][c2];

	int ans = INF;
	for (int i = r1; i < r2; i++) ans = min(ans, solve(r1, c1, i, c2) + solve(i + 1, c1, r2, c2));
	for (int i = c1; i < c2; i++) ans = min(ans, solve(r1, c1, r2, i) + solve(r1, i + 1, r2, c2));
	return dp[r1][c1][r2][c2] = ans + grid[r2][c2] - grid[r1 - 1][c2] - grid[r2][c1 - 1] + grid[r1 - 1][c1 - 1];
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> grid[i][j];

	for (int i = 1; i < N; i++) grid[i][0] += grid[i - 1][0];
	for (int i = 1; i < M; i++) grid[0][i] += grid[0][i - 1];
	for (int i = 1; i < N; i++)
		for (int j = 1; j < M; j++)
			grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];

	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0, N - 1, M - 1) << '\n';
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 14 ms 24832 KB Output is correct
2 Correct 15 ms 24832 KB Output is correct
3 Incorrect 14 ms 24832 KB Output isn't correct
4 Incorrect 14 ms 24832 KB Output isn't correct
5 Correct 14 ms 24832 KB Output is correct
6 Incorrect 15 ms 24832 KB Output isn't correct
7 Incorrect 15 ms 24832 KB Output isn't correct
8 Incorrect 25 ms 24832 KB Output isn't correct
9 Correct 34 ms 24952 KB Output is correct
10 Incorrect 45 ms 24832 KB Output isn't correct
11 Correct 40 ms 24952 KB Output is correct
12 Incorrect 106 ms 24832 KB Output isn't correct
13 Correct 183 ms 24952 KB Output is correct
14 Correct 56 ms 24832 KB Output is correct
15 Correct 217 ms 24952 KB Output is correct
16 Incorrect 30 ms 24832 KB Output isn't correct
17 Incorrect 92 ms 24864 KB Output isn't correct
18 Correct 536 ms 24952 KB Output is correct
19 Incorrect 883 ms 24872 KB Output isn't correct
20 Incorrect 1012 ms 25080 KB Output isn't correct