Submission #413532

#	Time	Username	Problem	Language	Result	Execution time	Memory
413532		aryan12	Orchard (NOI14_orchard)	C++17	25 / 25	320 ms	33612 KiB

orchard

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() {
	int n, m;
	cin >> n >> m;
	int total = 0;
	int a[n + 1][m + 1];
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			total += a[i][j];
			if(a[i][j] == 0) {
				a[i][j] = -1;
			}
		}
	}
	int grid[n + 1][m + 1];
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= m; j++) {
			grid[i][j] = 0;
		}
	}
	grid[1][1] = a[1][1];
	for(int i = 2; i <= n; i++) {;
		grid[i][1] = grid[i - 1][1] + a[i][1];
	}
	for(int i = 2; i <= m; i++) {
		grid[1][i] = grid[1][i - 1] + a[1][i];
	}
	for(int i = 2; i <= n; i++) {
		for(int j = 2; j <= m; j++) {
			grid[i][j] = grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1] + a[i][j];
		}
	}
	/*for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cout << grid[i][j] << " ";
		}
		cout << "\n";
	}*/
	//cout << "total = " << total << "\n";
	int ans = INT_MAX;
	for(int left = 1; left <= n; left++) {
		for(int right = left; right <= n; right++) {
			int left_col = 0;
			for(int column = 1; column <= m; column++) {
				int sum = grid[right][column] - grid[left - 1][column] - grid[right][left_col] + grid[left - 1][left_col];
				int possible = (right - left + 1) * (column - left_col);
				int zeros = (possible - sum) / 2;
				int ones = total - (possible - zeros);
				ans = min(ans, zeros + ones);
				if(sum < 0) {
					left_col = column;
				}
			}
		}
	}
	cout << ans << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	return 0;
}

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