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

最近更新 : 2021-06-03 21:46

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


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