Submission #393830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393830	2021-04-24T15:58:17 Z	Berted	Raisins (IOI09_raisins)	C++14	100 / 100	426 ms	34360 KB

raisins

#include <iostream>
#define ll long long

using namespace std;

const ll INF = 1e15;

int N, M, pref[51][51];
ll DP[51][51][51][51];

inline int getSum(int y1, int x1, int y2, int x2) {return pref[y2][x2] - pref[y1 - 1][x2] - pref[y2][x1 - 1] + pref[y1 - 1][x1 - 1];}

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> pref[i][j];
			pref[i][j] += pref[i - 1][j];
			pref[i][j] += pref[i][j - 1];
			pref[i][j] -= pref[i - 1][j - 1];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (i == 0 && j == 0) continue;
			for (int k = 1; k + i <= N; k++)
			{
				for (int l = 1; l + j <= M; l++)
				{
					DP[k][l][k + i][l + j] = INF;
					for (int m = k; m < k + i; m++) DP[k][l][k + i][l + j] = min(DP[k][l][k + i][l + j], DP[k][l][m][l + j] + DP[m + 1][l][k + i][l + j]);
					for (int m = l; m < l + j; m++) DP[k][l][k + i][l + j] = min(DP[k][l][k + i][l + j], DP[k][l][k + i][m] + DP[k][m + 1][k + i][l + j]);
					DP[k][l][k + i][l + j] += getSum(k, l, k + i, l + j);
				}
			}
		}
	}

	cout << DP[1][1][N][M] << "\n";
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	844 KB	Output is correct
7	Correct	1 ms	1100 KB	Output is correct
8	Correct	4 ms	3404 KB	Output is correct
9	Correct	7 ms	4880 KB	Output is correct
10	Correct	10 ms	5880 KB	Output is correct
11	Correct	7 ms	4812 KB	Output is correct
12	Correct	33 ms	10436 KB	Output is correct
13	Correct	70 ms	13640 KB	Output is correct
14	Correct	10 ms	6064 KB	Output is correct
15	Correct	72 ms	15380 KB	Output is correct
16	Correct	6 ms	5324 KB	Output is correct
17	Correct	28 ms	11156 KB	Output is correct
18	Correct	221 ms	25684 KB	Output is correct
19	Correct	379 ms	31704 KB	Output is correct
20	Correct	426 ms	34360 KB	Output is correct