[人工智能]upc 2022/2/27 校赛b题 Boing

Klee was recently working on a potentially more powerful new type of bomb. However, she was not familiar with the new technology, and the quality of the bombs was not to her satisfaction.

Now, all the bombs Klee made form a square of size?nn, but due to the capacity of her bag, Klee can only take a few of the bombs, which means Klee can only choose a square of size?mm?and take away?kk?most powerful bombs among them.

Since Klee is busy with studying how to improve the power of bomb, she asks you to help her calculate what is the minimum power among all the bombs she can take.

Input

The input file contains only one test case.

The first line contains three integer?n,m,k(1≤m≤n≤103,1≤k≤m?m)n,m,k(1≤m≤n≤103,1≤k≤m?m), denoting the size of the whole square, the size which Klee can choose and the number of bombs Klee can take.

The following?nn?lines, each line contains of?nn?integers, the integer on the?i+1thi+1th?row and?jthjth?column denotes?ai,j(1≤ai,j≤109)ai,j(1≤ai,j≤109).

Output

The first line contains one integer?ansans, representing the minimum power of the?kthkth?biggest power of the bomb Klee can get.

Example

input

Copy

5 3 3
5 4 9 8 2
1 5 4 3 8
6 5 1 4 9
3 5 6 8 1
2 4 6 7 5

output

Copy

5

Note

In the sample, one possible way is that Klee can choose the square which left upper corner is located on the?1st1st?row and?1st1st?column and choose the bomb with power?9,6,59,6,5.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1010;
int n,m,k;
int a[maxn][maxn];
int d[maxn][maxn];
int sum[maxn][maxn];
bool check(int x)
{
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            if(a[i][j] > x) d[i][j] = 1;
            else d[i][j]=0;
        }
    }
    memset(sum,0,sizeof(sum));


    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + d[i][j];
        }
    }

    for(int i=m; i<=n; i++)
    {
        for(int j=m; j<=n; j++)
        {
            if(( sum[i][j] - sum[i][j-m] - sum[i-m][j] + sum[i-m][j-m])<k)
            {
                return true;
            }
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    int l=1,r=1e9;

    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

川哥的二维差分我还没看懂，不过用前缀和也能解决此题。