Problem : 33 - 最大子矩陣

Problem Statistics

Solved Member: 43　　Submission: 99　　User Tried: 47

Statement:

給定一個由整數所組成的正方形矩陣，其大小為N×N(亦即列、行數均為N)。令W為一矩形的框子，其大小為a×b (其中1<=a<=N，1<=b<=N)，則W 所形成之子矩陣為將W 置於該正方形矩陣內時，W 所框出的小矩陣。由於W 的大小及位置均可變動，因此可在給定的正方形矩陣中形成許多的子矩陣。請寫出一程式能找出一子矩陣，該矩陣中元素的加總值是所有子矩陣中最大的，稱為總和值最大的子矩陣；由於總和值最大的子矩陣可能有許多個，程式只要輸出總和值即可。

例如一個正方形矩陣如下：

則框線標示出來的就是總和值最大的子矩陣，總和值為60 + 93 + (-29) + 81 + 101 + 69 = 375。

程式計算如下：
　　首先必須依照輸入的兩個數值自動產生方形矩陣。
　　令正方型矩陣中第i列第j行的元素為aij(1<=i<=N；1<=j<=N)，則正方形矩陣為

其產生方式如下：給予N和a11，矩陣中的元素可根據下列式子自動產生。

再依據上述計算產生出的N×N 陣求出所有子矩陣中最大的總和值作為程式輸出。

Input:Output:

輸入檔可能包含多筆測試資料。
每筆測試資料佔一行，包含兩個整數。
第一個數字為矩陣大小N(2<=N<=300)；第二個數字為a11，兩個數之間以一個空白隔開。

對每筆測試資料請輸出最大子矩陣內元素總和。

Sample Input:Sample Output:

5 15
4 35
4 -85
5 13

375
149
178
185

HINT:

30% n<=10
60% n<=70
100% n<=300

Source:

93 北市賽

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1	2000ms	65536kb	10
2	2000ms	65536kb	10
3	2000ms	65536kb	10
4	2000ms	65536kb	10
5	2000ms	65536kb	10
6	2000ms	65536kb	10
7	2000ms	65536kb	10
8	2000ms	65536kb	10
9	2000ms	65536kb	10
10	2000ms	65536kb	10