d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)
Tags :
Accepted rate : 97人/113人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-25 10:56

Content

輸入一個整數二維矩陣 $A[M][N]$,另外給了一個整數 $K$,請計算哪一個子矩陣的和,也就是對所有 $1 \leq i \leq j \leq M$, $1 \leq p \leq q \leq N$,$\sum_{s=i}^j{\sum_{t=p}^q{A[s][t]}}$ 最接近 $K$ 而不超過 $K$。$M \leq 50$且 $NM \leq 300,000$,每一個整數的絕對值不超過 $3,000$。

Input

每筆測資的第一行有ㄧ個正整數 $K$;

第二行有兩個正整數 $M$ 與 $N$。

接下來,由上而下,從左至右,有 $M$ 行輸入,每一行有 $N$ 個整數,每一個整數的絕對值不超過 $3,000$,代表 $A[s][t]$,

同行整數間以空格隔開。

Output

在所有子矩陣和中,最接近 $K$ 但不超過 $K$ 的和。

Sample Input #1
6
2 3
-1 -1 1
2 2 2
Sample Output #1
6
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」