Submission #659805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
659805	2022-11-19T09:43:08 Z	Tob	Raisins (IOI09_raisins)	C++14	100 / 100	659 ms	83016 KB

raisins

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 57;

int n, m;
ll mat[N][N], ps[N][N];
ll dp[N][N][N][N];

ll f(int a1, int b1, int a2, int b2) {
	return ps[a2][b2] - ps[a1-1][b2] - ps[a2][b1-1] + ps[a1-1][b1-1];
}

ll DP(int a1, int b1, int a2, int b2) {
	if (dp[a1][b1][a2][b2] != -1) return dp[a1][b1][a2][b2];
	if (a1 == a2 && b1 == b2) {
		dp[a1][b1][a2][b2] = 0;
		return 0;
	}
	ll mn = 1e18;
	for (int i = a1; i < a2; i++) {
		mn = min(mn, DP(a1, b1, i, b2) + DP(i+1, b1, a2, b2));
	}
	for (int i = b1; i < b2; i++) {
		mn = min(mn, DP(a1, b1, a2, i) + DP(a1, i+1, a2, b2));
	}
	dp[a1][b1][a2][b2] = mn + f(a1, b1, a2, b2);
	return dp[a1][b1][a2][b2];
}

int main () {
	memset(dp, -1, sizeof dp);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + mat[i][j];
		}
	}
	
	cout << DP(1, 1, n, m);
	
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	82892 KB	Output is correct
2	Correct	31 ms	82892 KB	Output is correct
3	Correct	33 ms	82972 KB	Output is correct
4	Correct	33 ms	82904 KB	Output is correct
5	Correct	37 ms	82932 KB	Output is correct
6	Correct	35 ms	82856 KB	Output is correct
7	Correct	32 ms	82876 KB	Output is correct
8	Correct	46 ms	82920 KB	Output is correct
9	Correct	42 ms	82920 KB	Output is correct
10	Correct	50 ms	82892 KB	Output is correct
11	Correct	50 ms	82920 KB	Output is correct
12	Correct	87 ms	82952 KB	Output is correct
13	Correct	121 ms	82952 KB	Output is correct
14	Correct	56 ms	82920 KB	Output is correct
15	Correct	147 ms	82960 KB	Output is correct
16	Correct	46 ms	83016 KB	Output is correct
17	Correct	79 ms	82956 KB	Output is correct
18	Correct	370 ms	82968 KB	Output is correct
19	Correct	549 ms	82972 KB	Output is correct
20	Correct	659 ms	82972 KB	Output is correct