ZOJ Monthly, June 2012 F : Choir III

問題概要

H*W(H<100, W<2000)のボードがある。各マスには値と性別が決められている。負の値を含まず、男がB以上女がG以上いるような矩形内の値の和を最大化する問題。

解法

男の数、女の数、値、負の値の個数について累積和を計算しておく。そうすると矩形を決定すればO(1)で判定できて嬉しい。後はyhighとylowを全探索してx方向にしゃくとりすれば全体の計算量O(H^2*W)で間に合う。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int MAX_N = 100;
const int MAX_M = 2000;

int N, M, B, G;
int gender[MAX_N][MAX_M];
int64 value[MAX_N][MAX_M];
int64 accum_v[MAX_N + 1][MAX_M + 1];
int accum_nega[MAX_N + 1][MAX_M + 1];
int accum_man[MAX_N + 1][MAX_M + 1];
int accum_woman[MAX_N + 1][MAX_M + 1];

bool init() {
	if (scanf("%d%d%d%d", &N, &M, &B, &G) == EOF) {
		return false;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			scanf("%lld%d", value[i]+j, gender[i]+j);
		}
	}

	return true;
}

void solve() {

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			accum_v[i+1][j+1] = accum_v[i][j+1] + accum_v[i+1][j] - accum_v[i][j] + value[i][j];
			accum_nega[i+1][j+1] = accum_nega[i][j+1] + accum_nega[i+1][j] - accum_nega[i][j] + (value[i][j] < 0 ? 1 : 0);
			accum_man[i+1][j+1] = accum_man[i][j+1] + accum_man[i+1][j] - accum_man[i][j] + (gender[i][j] == 1 ? 1: 0);
			accum_woman[i+1][j+1] = accum_woman[i][j+1] + accum_woman[i+1][j] - accum_woman[i][j] + (gender[i][j] == 2 ? 1: 0);
		}
	}

	int64 ans = -1;
	for (int low_n = 0; low_n < N; ++low_n) {
		for (int high_n = low_n+1; high_n <= N; ++high_n) {
			int low_m = 0, high_m = 1;
			for (; low_m < M && high_m <= M; high_m++) {
				int boy = accum_man[high_n][high_m] - (accum_man[high_n][low_m] + accum_man[low_n][high_m]) + accum_man[low_n][low_m];
				int girl = accum_woman[high_n][high_m] - (accum_woman[high_n][low_m] + accum_woman[low_n][high_m]) + accum_woman[low_n][low_m];
				int nega = accum_nega[high_n][high_m] - (accum_nega[high_n][low_m] + accum_nega[low_n][high_m]) + accum_nega[low_n][low_m];
				int64 sum = accum_v[high_n][high_m] - (accum_v[high_n][low_m] + accum_v[low_n][high_m]) + accum_v[low_n][low_m];
				if (nega > 0) {
					low_m = high_m;
					continue;
				}
				if (boy >= B && girl >= G && sum > ans) {
					ans = sum;
				}
			}
		}
	}

	if (ans == -1) {
		puts("No solution!");
	}
	else {
		printf("%lld\n", ans);
	}
}

int main() {
	for (;init();) {
		solve();
	}

	return 0;
}