oj.uz

Submission #682945

# Submission time Handle Problem Language Result Execution time Memory
682945 2023-01-17T10:12:54 Z anonimy Orchard (NOI14_orchard) C++14
25 / 25
 728 ms 33492 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

ll getsum(ll i, ll j, ll k, ll h, vector<vector<ll>>& sum)
{
	return sum[i][j] - (k >= 0 ? sum[k][j] : 0) - (h >= 0 ? sum[i][h] : 0) + (k >= 0 && h >= 0 ? sum[k][h] : 0);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n, m;
	cin >> n >> m;

	vector<vector<ll>> map(n, vector<ll>(m));
	for (ll i = 0; i < n; i++)
		for (ll j = 0; j < m; j++)
			cin >> map[i][j];

	ll b = 0;
	for (ll i = 0; i < n; i++)
		for (ll j = 0; j < m; j++)
			if (map[i][j])
				b++;

	vector<vector<ll>> sum(n, vector<ll>(m, 0)), calc(n, vector<ll>(m, 0));

	sum[0][0] = map[0][0];
	calc[0][0] = (map[0][0] ? 1 : -1);

	for (ll i = 1; i < n; i++)
	{
		sum[i][0] = sum[i - 1][0] + map[i][0];
		calc[i][0] = calc[i - 1][0] + (map[i][0] ? 1 : -1);
	}

	for (ll j = 1; j < m; j++)
	{
		sum[0][j] = sum[0][j - 1] + map[0][j];
		calc[0][j] = calc[0][j - 1] + (map[0][j] ? 1 : -1);
	}

	for (ll i = 1; i < n; i++)
		for (ll j = 1; j < m; j++)
		{
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
			calc[i][j] = calc[i - 1][j] + calc[i][j - 1] - calc[i - 1][j - 1] + (map[i][j] ? 1 : -1);
		}

	ll minn = b;
	for (ll i = 0; i < n; i++)
	{
		for (ll k = 1; k <= n; k++)
		{
			ll last = -1;
			for (ll j = 0; j < m; j++)
			{
				ll curr = getsum(i, j, i - k, last, calc);

				if (curr < 0)
					last = j;
				else
					minn = min(minn, b - 2 * getsum(i, j, i - k, last, sum) + (k * (j - last)));
			}
		}
	}

	cout << minn;
}
/*
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
*/

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 33476 KB Output is correct
2 Correct 84 ms 33492 KB Output is correct
3 Correct 86 ms 33472 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6204 KB Output is correct
2 Correct 17 ms 6104 KB Output is correct
3 Correct 17 ms 6084 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct
2 Correct 20 ms 852 KB Output is correct
3 Correct 20 ms 852 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 19436 KB Output is correct
2 Correct 669 ms 19532 KB Output is correct
3 Correct 728 ms 19444 KB Output is correct