Submission #1113507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113507	2024-11-16T17:03:57 Z	Zflop	Raisins (IOI09_raisins)	C++14	100 / 100	216 ms	30412 KB

raisins

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
int N,M,A[2001][2001],dp[55][55][55][55];
void solve() {
	cin >> N >> M;
	for (int i = 1; i <= N;++i)
		for (int j = 1; j <= M;++j)
			for (int x = 1; x <= N;++x)
				for (int y = 1; y <= M;++y)
					dp[i][j][x][y] = (int)1e9;
	for (int i = 1; i <= N;++i)
		for (int j = 1; j <= M;++j) {
			cin >> A[i][j];
			dp[i][j][1][1] = 0;
			A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
			}
	
	auto combine = [&] (int i,int j,int x,int y,int len_row,int len_col) {
		int sum = A[i + len_row - 1][j + len_col - 1] + A[i - 1][j - 1] - A[i + len_row - 1][j - 1] - A[i - 1][j + len_col - 1];
		if (i == x) 
			return sum + dp[i][j][len_row][y - j] + dp[x][y][len_row][len_col - (y - j)];
		return sum + dp[i][j][x - i][len_col] + dp[x][y][len_row - (x - i)][len_col];
		};
	
	for (int len_row = 1; len_row <= N;++len_row) {
		for (int len_col = 1; len_col <= M;++len_col)
			for (int i = 1; i <= N - len_row + 1;++i)
				for (int j = 1; j <= M - len_col + 1;++j) {
					for (int x = i + 1; x <= i + len_row  - 1;++x) // tai pe orizontala
						dp[i][j][len_row][len_col] = min(dp[i][j][len_row][len_col],combine(i,j,x,j,len_row,len_col));
					for (int y = j + 1; y <= j + len_col - 1;++y)
						dp[i][j][len_row][len_col] = min(dp[i][j][len_row][len_col],combine(i,j,i,y,len_row,len_col));
				}
		}
	cout << dp[1][1][N][M];
	}
// dp[a][b][x][y] - varfurile stanga sus si dreapta jos a unui dreptunghi
// sau mai usor sa il vad ca pe dp[a][b][len_row][len_col], ca sa am cv dupa ce le pot masura
int main() {
	solve();
	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	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	592 KB	Output is correct
6	Correct	1 ms	1104 KB	Output is correct
7	Correct	2 ms	1528 KB	Output is correct
8	Correct	5 ms	3536 KB	Output is correct
9	Correct	7 ms	5200 KB	Output is correct
10	Correct	8 ms	6224 KB	Output is correct
11	Correct	7 ms	5200 KB	Output is correct
12	Correct	24 ms	11328 KB	Output is correct
13	Correct	40 ms	14416 KB	Output is correct
14	Correct	10 ms	6480 KB	Output is correct
15	Correct	50 ms	16208 KB	Output is correct
16	Correct	8 ms	5880 KB	Output is correct
17	Correct	23 ms	11088 KB	Output is correct
18	Correct	127 ms	23624 KB	Output is correct
19	Correct	186 ms	28496 KB	Output is correct
20	Correct	216 ms	30412 KB	Output is correct