oj.uz

Submission #413532

# Submission time Handle Problem Language Result Execution time Memory
413532 2021-05-28T20:41:28 Z aryan12 Orchard (NOI14_orchard) C++17
25 / 25
 320 ms 33612 KB 
#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.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 33472 KB Output is correct
2 Correct 99 ms 33612 KB Output is correct
3 Correct 96 ms 33488 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5320 KB Output is correct
2 Correct 20 ms 5332 KB Output is correct
3 Correct 20 ms 5336 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 10 ms 720 KB Output is correct
3 Correct 10 ms 664 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 13692 KB Output is correct
2 Correct 310 ms 13584 KB Output is correct
3 Correct 320 ms 13596 KB Output is correct