作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的。所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。
首都都被认为是一个占地 $C \times C$ 的正方形。小 Z 希望你找到一个合适的位置，使得首都所占领的位置的土地价值总和最高。

输入格式

  • 第一行三个整数 $N, M, C$，表示地图的宽和长以及首都的边长。
  • 接下来 $N$ 行每行 $M$ 个整数，表示地图上每个地块的价值。价值可能为负数。

    输出格式

  • 一行两个整数 $X, Y$，表示首都左上角的坐标。

    输入输出样例

  • 输入 #1：
    Plaintext 
    3 4 2
    1 2 3 1
    -1 9 0 2
    2 0 1 1
  • 输出 #1：
    Plaintext 
    1 2

二维前缀和

#include<iostream>
using namespace std;
int main(){
    int N,M,C,X,Y,MAXVAULE=0;
    cin>>N>>M>>C;
    int arr[N+1][M+1];
    for(int i=0;i<=M;i++)
    arr[0][i]=-2e18;
    for(int i=0;i<=N;i++)
    arr[i][0]=-2e18;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        cin>>arr[i][j];
    }

    for(int i=1;i<=N;i++)
    {
        for(int j=2;j<=M;j++)
        arr[i][j]+=arr[i][j-1];
    }

    for(int j=1;j<=M;j++)
    {
        for(int i=2;j<=N;j++)
        arr[i][j]+=arr[i-1][j];
    }
    for(int i=C;i<=N;i++)
    {
        for(int j=C;j<=M;j++)
        {
            if(arr[i][j]-arr[i][j-C]-arr[i-C][j]+arr[i+C][j+C]>MAXVAULE)
            {
                MAXVAULE=arr[i][j]-arr[i][j-C]-arr[i-C][j]+arr[i+C][j+C];
                X=i-C+1,Y=j-C+1;
            }
        }

    }
    cout<<X<<" "<<Y;
}