Submission #719015

#	Time	Username	Problem	Language	Result	Execution time	Memory
719015		NintsiChkhaidze	Raisins (IOI09_raisins)	C++14	100 / 100	1052 ms	37128 KiB

raisins

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define int ll
using namespace std;
 
const int N = 55,inf = 1e18;

int a[N][N],dp[N][N][N][N];

int get(int l1,int r1,int l2,int r2){
	if (dp[l1][r1][l2][r2] != inf) return dp[l1][r1][l2][r2];
	if (l1 == l2 && r1 == r2) return dp[l1][r1][l2][r2] = 0;
	
 	int sum=0,ans=inf;
	for (int i=l1;i<=l2;i++)
		for (int j=r1;j<=r2;j++)
			sum+=a[i][j];
	
	for (int i = l1; i < l2; i++){
		int res = sum + get(l1,r1,i,r2) + get(i + 1,r1,l2,r2);
		ans = min(ans,res);
	}
	
	for (int j = r1; j < r2; j++){
		int res = sum + get(l1,r1,l2,j) + get(l1,j + 1,l2,r2);
		ans = min(ans,res);
	}
	return dp[l1][r1][l2][r2] = ans;
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    	
	int n,m;
	cin>>n>>m;
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	
	for (int l1=1;l1<=n;l1++)
		for (int r1=1;r1<=m;r1++)
			for (int l2=l1;l2<=n;l2++)
				for (int r2 =r1;r2<=m;r2++)
					dp[l1][r1][l2][r2] = inf;
	
	cout<<get(1,1,n,m)<<"\n";
}

• Subtask 1: 100 / 100