1686--【USACO】Happy Cows

1686: 【USACO】Happy Cows

时间限制: 1.000 Sec  内存限制: 64 MB
提交: 9  解决: 3
[提交] [状态] [报告] [命题人:]


While standing in a perfect N x M (1 <= N,M <= 50) rectangle, the herd of Farmer John's cows has been reading psychology books together. One book had a test to rate "happiness" so each calculated their "happiness rating", an integer range from -100..100 inclusive. Another book suggested that a sub-rectangle of cows has an aggregate happiness rating that is the product of all the happiness ratings for the individual cows of the sub-rectangle. This is interesting in that two unhappy cows pretty much cancel each other's unhappiness while wallowing in each other's self-pity. Find the happiest sub-rectangle of the herd of cows. A sub-rectangle is a p x q rectangle of contiguous cows culled from the larger herd.


* Line 1: Two integers: N and M. * Line 2..N + 1: Each line contains M integers that tell the cows' happiness ratings; line 2 is row 1, etc. The first integer on each line is is column 1, etc.


A single line with four integers that define the happiest sub-group. The first two integers are the (row,column) position of the upper left corner of the happiest sub-rectangle The next two integers are the (row,column) position of the lower right corner of the happiest sub-rectangle In the case where more than one sub-rectangle has the maximum product, output the one with the smallest number of elements. If more than one has the smallest number of elements, output the one the most left, and if more than one is most left, output the sub-rectangle closer to the top.


输入  复制
4 2 -1 4 5 3 -6 -2 2 1
输出  复制
2 1 4 2