UOJ Logo

NOI.AC

1S 512MB

#328. money

Statistics

【问题描述】

小明在玩大富翁游戏,学习做房地产生意,游戏是这样的,有一个由n×n个格子组成的地图,每个格子代表一块土地,并且有一个价格,现在小明要做的是找一块矩形的区域,并且这个矩形的土地价格总和位于[k,2k]

【输入格式】

第一行,k、 n 第二行开始是一个$n \times n$的地图

【输出格式】

输出矩形的左上和右下的列-行坐标或NIE

【输入输出样例 1】

in
4  3
1  1  1
1  9  1
1  1  1
out
NIE

【输入输出样例 2】

out
8  4
1  2  1  3
25  1  2  1
4  20  3  3
3  30  12  2
out
2 1 4 2

【数据规模与约定】

35% 的数据,n <= 10

60% 的数据,n <= 200

100% 的数据,n <= 2000 1<=k<=10^9 每个价格都是不大于$2 \times 10^9$的非负整数

注意数据有明显梯度。