سبز به اندازه کافی
Problem
چراگاه کشاورز جان را می توان به عنوان یک شبکه
NxN (
\(1<=N<=500\)) از سلول های مربعی در نظر گرفت. با چمن (مانند یک صفحه شطرنج بزرگ). به دلیل تنوع خاک، چمن در برخی از سلول ها سبزتر از سایر سلول ها است. هر سلول
(i,j) با یک عدد صحیح توصیف می‌شود - سطح سبزی
G(i,j)، در بازه
\ (1…200\).
کشاورز جان می‌خواهد از یک شبکه مستطیلی فرعی مرتعش عکس بگیرد. او می خواهد که حداقل G در عکسش شارپ 100 باشد. به او کمک کنید شمارش کند که چند عکس مختلف می تواند بگیرد. اندازه زیرشبکه می تواند از کل مرتع تا یک سلول متغیر باشد. \(N^2(N+1)^2/4\) شبکه های فرعی مختلفی وجود دارد، از یک عدد صحیح 64 بیتی (مانند < code>long) استفاده کنید long در C++).
ورودی
خط اول حاوی
N است. هر یک از
N خطوط زیر حاوی
N اعداد صحیح است و با هم بزرگی ها را توصیف می کنند
G(i,j) ; ;برای مرتع
NхN .
حصر
تعداد عکس‌های مختلفی را که کشاورز جان می‌تواند بگیرد، خروجی بگیرید. تعداد زیرشبکه های مستطیلی که حداقل سطح "سبزی" در آنها وجود دارد. دقیقا
100.
توجه داشته باشید که پاسخ به یک متغیر عدد صحیح 64 بیتی از نوع long در C++ نیاز دارد.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |