oj.uz

Submission #682947

# Submission time Handle Problem Language Result Execution time Memory
682947 2023-01-17T10:20:34 Z anonimy Orchard (NOI14_orchard) C++14
25 / 25
 661 ms 31752 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++;

	//sum[i][j] = how many bananas are in this prefix
	//calc[i][j] = how many bananas against apples
	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);
		}

	// we will look at a rectngle that starts at i,j and has width of k, and substruct negative prefixes
	ll minn = b;
	for (ll i = 0; i < n; i++)
	{
		for (ll k = 1; k <= n; k++)
		{
			//last negative prefix
			ll last = -1;
			for (ll j = 0; j < m; j++)
			{
				ll curr = getsum(i, j, i - k, last, calc);

				//we don't want negtive prefixes 
				if (curr < 0)
					last = j;
				else
					minn = min(minn, b - 2 * getsum(i, j, i - k, last, sum) + (k * (j - last)));
			}
		}
	}

	cout << minn;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 1 ms 724 KB Output is correct
2 Correct 2 ms 712 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 77 ms 31688 KB Output is correct
2 Correct 71 ms 31752 KB Output is correct
3 Correct 73 ms 31708 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5864 KB Output is correct
2 Correct 16 ms 5928 KB Output is correct
3 Correct 15 ms 5892 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 23 ms 808 KB Output is correct
3 Correct 29 ms 852 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 18100 KB Output is correct
2 Correct 661 ms 18100 KB Output is correct
3 Correct 643 ms 18100 KB Output is correct