Submission #265286

#	Time	Username	Problem	Language	Result	Execution time	Memory
265286		T0p_	Orchard (NOI14_orchard)	C++14	25 / 25	427 ms	25824 KiB

orchard

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

int dp[155][155][2];

int main()
{
	int n, m;
	scanf(" %d %d",&n,&m);
	int arr[n+5][m+5];
	memset(arr, 0, sizeof arr);
	for(int i=1 ; i<=n ; i++)
		for(int j=1 ; j<=m ; j++)
		{
			scanf(" %d",&arr[i][j]);
			arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
		}
	int ans = 1e9;
	for(int sz=1 ; sz<=n ; sz++)
		for(int i=1 ; i<=n ; i++)
		{
			int j = i+sz-1;
			if(j > n) break ;
			for(int k=1 ; k<=m ; k++)
			{
				dp[i][j][k%2] = min(dp[i][j][(k-1)%2], arr[j][k-1] - arr[i-1][k-1]) + sz - arr[j][k] + arr[j][k-1] + arr[i-1][k] - arr[i-1][k-1];
				ans = min(ans, dp[i][j][k%2] + arr[j][m] - arr[j][k] + arr[i-1][k] + arr[n][m] - arr[j][m]);
			}
		}
	printf("%d\n",ans);
	return 0;
}

// dp[i][j][k] -> row ith to row jth, col 1st to col kth and end the second area on col kth
/*
5 7
0 0 1 0 0 1 0
0 1 1 1 1 1 0
0 1 1 0 0 1 0
0 1 1 1 1 1 0
0 0 1 0 0 1 0
*/

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5