oj.uz

Submission #962583

# Submission time Handle Problem Language Result Execution time Memory
962583 2024-04-13T21:35:18 Z starchan Raisins (IOI09_raisins) C++17
100 / 100
 123 ms 57716 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 52;

int a[MX][MX];
int dp[MX][MX][MX][MX];

int C(int lx, int rx, int ly, int ry)
{
	return a[rx][ry]-a[rx][ly-1]-a[lx-1][ry]+a[lx-1][ly-1];
}

int solve(int lx, int rx, int ly, int ry)
{
	if(dp[lx][rx][ly][ry] != -1)
		return dp[lx][rx][ly][ry];
	int val = INF;
	for(int mx = lx; mx < rx; mx++)
		val = min(val, solve(lx, mx, ly, ry)+solve(mx+1, rx, ly, ry));
	for(int my = ly; my < ry; my++)
		val = min(val, solve(lx, rx, ly, my)+solve(lx, rx, my+1, ry));
	if(val == INF)
		return dp[lx][rx][ly][ry] = 0;
	else
		return dp[lx][rx][ly][ry] = C(lx, rx, ly, ry)+val;
}

signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	for(auto &i: dp)
		for(auto &j: i)
			for(auto &k: j)
				for(auto &l: k)
					l = -1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
			cin >> a[i][j];
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
			a[i][j]+=a[i][j-1];
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
			a[i][j]+=a[i-1][j];
	}
	cout << solve(1, n, 1, m) << "\n";
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 57548 KB Output is correct
2 Correct 9 ms 57692 KB Output is correct
3 Correct 9 ms 57692 KB Output is correct
4 Correct 9 ms 57688 KB Output is correct
5 Correct 9 ms 57692 KB Output is correct
6 Correct 8 ms 57692 KB Output is correct
7 Correct 8 ms 57500 KB Output is correct
8 Correct 9 ms 57688 KB Output is correct
9 Correct 11 ms 57520 KB Output is correct
10 Correct 13 ms 57708 KB Output is correct
11 Correct 13 ms 57492 KB Output is correct
12 Correct 18 ms 57692 KB Output is correct
13 Correct 25 ms 57692 KB Output is correct
14 Correct 14 ms 57692 KB Output is correct
15 Correct 29 ms 57716 KB Output is correct
16 Correct 10 ms 57548 KB Output is correct
17 Correct 23 ms 57576 KB Output is correct
18 Correct 68 ms 57696 KB Output is correct
19 Correct 115 ms 57688 KB Output is correct
20 Correct 123 ms 57596 KB Output is correct