HDU 4721 Food and Productivity

In the Game Civilization X, the world is made up of square-shaped "tiles", forming a rectangle on the world map. For a tile located at row X and column Y , we give it a coordinate, say (X, Y ). 

As you can see, different tiles have different "terrain-types", so they may have different amount of Resources. In this problem, we only consider two of them: Food and Productivity. 

An important step in the Game is building cities. After you choose a tile to build a city, the Food amount in that tile will increase by A, and the Productivity amount will increase by B, no other tiles will be changed. 

You decide to build your first city on the map, as an experienced player, you will choose the best tile on the map, here is how you make up your mind: 

For each tile (X, Y ), you set up an "Influence Range" of that tile. Each tile (x 

i, y 

i) is said to be within the range if the following equation holds: 

max(|X - x 

i| , |Y - y 

i|) <= R

After checking all the tiles within that range, you will get two values: the sum of all those tiles' Food amount, and the sum of all those tiles' Productivity. Among those two values, the final score for tile (X, Y ) will be the smaller one. 

When choosing tiles, you just choose the tile with the highest score to build your city. 

You are given a map with size N * M, and you wonder, for different values of A and B, what is the highest score for your first city?

Input

The first line has a number T (T <= 10) , indicating the number of test cases. 

For each test case, first line has four numbers N, M, R and Q (1 <= N, M <= 500, 0 <= 2 * R + 1 <= min(N,M), Q <= 200000), which is the size of the map. 

Then come N lines each with M numbers, they are the original Food (0 < Food <= 3) amount for each tile. 

Then come N lines each with M numbers, they are the original 

Productivity 

(0 < 

Productivity <= 3) amount for each tile. 

Then come Q lines each with two numbers A and B (0 <= A, B <= 10 

6). Each is a query for you to answer. Those queries will not affect each other.

Output

For test case X, output \Case #X:" first, in a single line. 

Then output Q lines, each with an answer. 

There should be a blank line 

*BETWEEN* each test case.

Sample Input

1

3 3 0 2

1 2 1

1 1 1

1 1 1

1 1 1

1 2 1

1 1 1

1 2

2 1

Sample Output

Case #1:

3

3

计算出以每个点为中心的正方形的两个权值和，然后根据第一个排序。

#include<map>   
#include<set>  
#include<ctime>    
#include<cmath>   
#include<stack>
#include<queue>     
#include<string>    
#include<vector>    
#include<cstdio>        
#include<cstring>      
#include<iostream>    
#include<algorithm>        
#include<functional>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))        
#define rep(i,j,k) for(int i=j;i<=k;i++)        
#define per(i,j,k) for(int i=j;i>=k;i--)        
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])        
#define inone(x) scanf("%d",&x)        
#define intwo(x,y) scanf("%d%d",&x,&y)        
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)      
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)     
#define lson x<<1,l,mid    
#define rson x<<1|1,mid+1,r    
#define mp(i,j) make_pair(i,j)    
#define ff first    
#define ss second    
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 5e2 + 10;
const double eps = 1e-8;
int T, n, m, r, q, sz, cas = 1, x, y;
int a[N][N], b[N][N], c[N][N], d[N][N], mx[N*N];
pii g[N*N];

bool check(int z)
{
  int k = lower_bound(g, g + sz, mp(z - x, 0)) - g;
  return k < sz && mx[k] + y >= z;
}

int main()
{
  for (inone(T); T--; cas++)
  {
    infou(n, m, r, q);
    rep(i, 1, n) rep(j, 1, m) inone(a[i][j]);
    rep(i, 1, n) rep(j, 1, m) inone(b[i][j]);
    rep(i, 1, n) rep(j, 1, m)
    {
      c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i][j];
      d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + b[i][j];
    }
    sz = 0;
    rep(i, 1, n) rep(j, 1, m)
    {
      int rx = min(i + r, n), ry = min(j + r, m);
      int lx = max(i - r, 1) - 1, ly = max(j - r, 1) - 1;
      g[sz++] = mp(c[rx][ry] + c[lx][ly] - c[rx][ly] - c[lx][ry], d[rx][ry] + d[lx][ly] - d[rx][ly] - d[lx][ry]);
    }
    sort(g, g + sz); mx[sz] = 0;
    per(i, sz - 1, 0) mx[i] = max(mx[i + 1], g[i].ss);
    printf("Case #%d:\n", cas);
    while (q--)
    {
      intwo(x, y);
      int l = 0, r = 2e6;
      while (l <= r)
      {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1; else r = mid - 1;
      }
      printf("%d\n", r);
    }
    if (T) putchar(10);
  }
  return 0;
}