f737.
農地 (Farmland)
內容
一位農夫買了一塊荒地，想要開墾成良田，但是後來發現開墾整塊土地的成本太高，而且荒地上可能會有他不想要砍掉的大樹，於是他決定只開墾部分的土地。首先，這塊荒地的長與寬均為 N 公尺，農夫將其等分為 N × N 格 1 公尺 × 1公尺的小方格，針對每一個方格農夫都會算出其開墾的成本開墾的總成本為所有要開墾方格的成本加總，還有如果該方格是大樹的話，農夫絕對不會將它納入開墾的範圍。農夫想要開墾出一塊正方形的農地，在給定開墾總預算 U 以及每一格整地成本的情況之下，算出農夫最多可以得到多大平方公尺的正方形良田。舉例而言：假設 N =5，U =10 土地資訊如下圖所示(如果該格的值為 -1表示為大樹，否則該值為開墾成本)，最佳解為開墾藍色方格 ，因為開墾總預算為 1+2+6+1 10 至於紅色方格的開墾總預算為 1+1+2+6+1+1+1+1+1+1=16>10 、橘色方格包含大樹，所以都無法成為最佳解。
輸入說明
第一行有2個正整數 N 和 U (1 <= N <= 3000, 1 <= U <= 109) 分別表示正方形荒地的邊長以及開墾的總預算。接下來N行和每行都有N個整數a(-1 ≤ a ≤ 100)，兩兩之間都用一個空白隔開，代表該格荒地的開墾成本，如果a為 -1，代表該格為大樹。
輸出說明
第一行請輸出一個非負整數表示依照上述規則，農夫最大可以開墾的面積也就是格子總數。如果不存在合乎預算的解，輸出 0。
範例輸入
#1
5 10 1 2 -1 3 4 2 0 1 0 1 -1 2 6 1 1 0 0 0 0 1 -1 0 1 1 1
範例輸出
#1
9
範例輸入
#2
2 9 -1 10 10 -1
範例輸出
#2
0
範例輸入
#3
3 2 2 2 2 2 2 2 2 2 2
範例輸出
#3
1
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <50M
公開 測資點#5 (10%): 1.0s , <50M
公開 測資點#6 (10%): 2.0s , <50M
公開 測資點#7 (10%): 2.0s , <50M
公開 測資點#8 (10%): 2.0s , <50M
公開 測資點#9 (10%): 2.0s , <50M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <50M
公開 測資點#5 (10%): 1.0s , <50M
公開 測資點#6 (10%): 2.0s , <50M
公開 測資點#7 (10%): 2.0s , <50M
公開 測資點#8 (10%): 2.0s , <50M
公開 測資點#9 (10%): 2.0s , <50M
提示 ：
第一組 10分 1 <= N <= 10
第二組 20分 1 <= N <= 100
第三組 30分 1 <= N <= 3000, U =10^9
第四組 40分 1 <= N <= 3000
測資為隨機產生，若有錯誤或是加強測資歡迎提出
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 36602 |
|
f737 | 299 | 2023-07-26 20:57 |