Submission #405612

#	Time	Username	Problem	Language	Result	Execution time	Memory
405612		Jasiekstrz	Raisins (IOI09_raisins)	C++17	100 / 100	181 ms	18372 KiB

raisins

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e9+7;
const int N=50;
int tab[N+10][N+10];
int pref[N+10][N+10];
int dp[N+10][N+10][N+10][N+10];
int sum(int li,int ri,int lj,int rj)
{
	return pref[ri][rj]-pref[ri][lj-1]-pref[li-1][rj]+pref[li-1][lj-1];
}
int main()
{
	ios_base::sync_with_stdio(false);
	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>>tab[i][j];
			pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+tab[i][j];
		}
	}
	for(int di=0;di<=n;di++)
	{
		for(int dj=(di==0 ? 1:0);dj<=m;dj++)
		{
			for(int li=1,ri=di+1;ri<=n;li++,ri++)
			{
				for(int lj=1,rj=dj+1;rj<=m;lj++,rj++)
				{
					dp[li][ri][lj][rj]=INF;
					for(int k=li;k<ri;k++)
						dp[li][ri][lj][rj]=min(dp[li][ri][lj][rj],
								dp[li][k][lj][rj]+dp[k+1][ri][lj][rj]);
					for(int k=lj;k<rj;k++)
						dp[li][ri][lj][rj]=min(dp[li][ri][lj][rj],
								dp[li][ri][lj][k]+dp[li][ri][k+1][rj]);
					dp[li][ri][lj][rj]+=sum(li,ri,lj,rj);
				}
			}
		}
	}
	cout<<dp[1][n][1][m]<<"\n";
	return 0;
}

• Subtask 1: 100 / 100