제출 #682947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682947		anonimy	과수원 (NOI14_orchard)	C++14	25 / 25	661 ms	31752 KiB

orchard

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5