(UVA) 11951 - Area

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3102&mosmsg=Submission+received+with+ID+17707156

沒想到這題 O(n^3 lg n)可以過~~ (搞不好n^4也可以過XD)

基本想法是：枚舉x1,x2,y1,利用二分搜找y2

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAX_N = 102;

LL sum[MAX_N][MAX_N];
LL row[MAX_N][MAX_N]; //a[1~x][1~y]
LL col[MAX_N][MAX_N];

int main () {
 int T;
 scanf("%d",&T);
 for (int qq=1;T>=qq;qq++) {
  printf("Case #%d: ",qq);
  memset(sum,0,sizeof(sum));
  LL n,m,k;
  scanf("%lld %lld %lld",&n,&m,&k);
  for (int x=1;n>=x;x++) {
   for (int y=1;m>=y;y++) {
    int p;
    scanf("%d",&p);
    sum[x][y] = sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] + p;
   }
  }
//  for (int x=1;n>=x;x++) {
//   for (int y=1;n>=y;y++) {
//    cout<<sum[x][y]<< ' ';
//   }
//   cout<<endl;
//  }
  LL ans1=0,ans2=0;
  for (int x1=1;n>=x1;x1++) {
   for (int y1=1;m>=y1;y1++) {
    for (int x2=x1;n>=x2;x2++) {
     //binary got y2
     int L=y1-1,R=m+1;
     while (R-L!=1) {
      int mid=(L+R)>>1;
      LL t=sum[x2][mid] + sum[x1-1][y1-1] - sum[x2][y1-1] - sum[x1-1][mid];
      if (t<=k) {
       L=mid;
      }
      else {
       R=mid;
      }
     }
     LL t=sum[x2][L] + sum[x1-1][y1-1] - sum[x2][y1-1] - sum[x1-1][L];
     if (t<=k) {
      if ((x2-x1+1) * (L-y1+1) > ans1) {
       ans1=(x2-x1+1) * (L-y1+1);
       ans2=t;
      }
      else if ((x2-x1+1) * (L-y1+1) == ans1 && t<ans2) ans2=t;
     }
    }
   }
  }
  printf("%lld %lld\n",ans1,ans2);
 }
}