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; }