Toggle navigation
PIPIOJ
F.A.Qs
Web Board
ProblemSet
Source/Category
Status
Ranklist
Contest
Recent
Login
Problem1460--矩阵问题(弱化版)
1460: 矩阵问题(弱化版)
Time Limit:
1 Sec
Memory Limit:
128 MB
Submit:
84
Solved:
47
[
Submit
] [
Status
] [
Web Board
] [Creator:
]
Description
给定一个n*n的矩阵,你可以从矩阵中任选一块正方形,但必须保证该正方形中所有数字之和小于等于m。
请问以(i,j)为左上角且符合以上要求的正方形中,边长最大的是多少?
Input
第一行两个正整数n,m,其中n<=300,m<=10^9。
接下来n行,每行n个非负整数aij,aij<=10^9。
Output
输出n行,每行n个数字。其中第i行第j个数字表示,以(i,j)为左上角且符合题目要求的正方形的最大边长。若以(i,j)为左上角没有符合要求的正方形,则输出0。
Sample Input
3 4 1 1 1 1 1 1 1 1 1
Sample Output
2 2 1 2 2 1 1 1 1
Source/Category
简单
前缀和