oj.uz

Submission #265286

# Submission time Handle Problem Language Result Execution time Memory
265286 2020-08-14T14:51:17 Z T0p_ Orchard (NOI14_orchard) C++14
25 / 25
 427 ms 25824 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 25784 KB Output is correct
2 Correct 135 ms 25720 KB Output is correct
3 Correct 144 ms 25824 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3456 KB Output is correct
2 Correct 24 ms 3456 KB Output is correct
3 Correct 25 ms 3456 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 13 ms 640 KB Output is correct
3 Correct 13 ms 640 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 4984 KB Output is correct
2 Correct 427 ms 4984 KB Output is correct
3 Correct 421 ms 4984 KB Output is correct