Submission #231929

#	Time	Username	Problem	Language	Result	Execution time	Memory
231929		T0p_	Raisins (IOI09_raisins)	C++14	100 / 100	402 ms	37240 KiB

raisins

#include<bits/stdc++.h>
using namespace std;

long long arr[55][55], dp[55][55][55][55];

long long cost(int a, int b, int c, int d)
{
	return arr[c][d] - arr[a-1][d] - arr[c][b-1] + arr[a-1][b-1];
}

int main()
{
	int n, m;
	scanf(" %d %d",&n,&m);
	for(int i=1 ; i<=n ; i++)
	{
		for(int j=1 ; j<=m ; j++)
		{
			scanf(" %lld",&arr[i][j]);
			arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
		}
	}

	for(int size_i=1 ; size_i<=n ; size_i++)
	{
		for(int size_j=1 ; size_j<=m ; size_j++)
		{
			for(int si=1 ; si<=n ; si++)
			{
				for(int sj=1 ; sj<=m ; sj++)
				{
					int ei = si + size_i - 1, ej = sj + size_j - 1;
					if(ei > n || ej > m || (si == ei && sj == ej)) continue ;
					long long opt = 1e15;
					for(int k=si ; k<ei ; k++)
					{
						opt = min(opt, dp[si][sj][k][ej] + dp[k+1][sj][ei][ej] + cost(si, sj, ei, ej));
					}
					for(int k=sj ; k<ej ; k++)
					{
						opt = min(opt, dp[si][sj][ei][k] + dp[si][k+1][ei][ej] + cost(si, sj, ei, ej));
					}
					dp[si][sj][ei][ej] = opt;
				}
			}
		}
	}
	printf("%lld\n",dp[1][1][n][m]);
	return 0;
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~
raisins.cpp:19:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %lld",&arr[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100