Submission #1113507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113507		Zflop	Raisins (IOI09_raisins)	C++14	100 / 100	216 ms	30412 KiB

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 / 100