題目描述

給定?𝑛×𝑛n×n?個整數組成一個方陣?𝑎𝑖,𝑗ai,j?，請找一個?𝑘×𝑘k×k?的子方陣，使得子方陣內的數字之和達到最大，輸出這個最大值。

輸入格式

• 第一行：兩個整數?𝑛n?與?𝑘k
• 第二行到第?𝑛+1n+1?行：每行?𝑛n?個整數表示?𝑎𝑖,𝑗ai,j?

輸出格式

單個整數：表示最大的?𝑘×𝑘k×k?的子方陣的數字之和。

數據范圍

• 30%30%?的數據，1≤𝑘≤𝑛≤301≤k≤n≤30
• 60%60%?的數據，1≤𝑘≤𝑛≤3001≤k≤n≤300
• 100%100%?的數據，1≤𝑘≤𝑛≤25001≤k≤n≤2500
• 0≤𝑎𝑖,𝑗≤1,000,0000≤ai,j?≤1,000,000

樣例數據

輸入:

3 2
1 2 3
3 1 2
0 2 4

輸出:

9

說明:

右下角最大

詳見代碼:

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[3005][3005];
long long ans=0;
int b;
int main() 
{scanf("%d %d",&n,&k);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){scanf("%d",&b);a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+b;}}for (int j=k;j<=n;j++){for (int i=k;i<=n;i++){ans=max(ans,a[i][j]-a[i][j-k]-a[i-k][j]+a[i-k][j-k]);}}printf("%lld",ans);return 0;
}