Responsive image

问题 H: 煜的子矩形

问题 H: 煜的子矩形

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

煜拿到了一个n行m列的矩阵，矩阵中每个元素的权值由a数组和b数组决定。第ii行第jj列的元素为ai∗bj。
煜希望选择一个子矩形，使得该子矩形所有元素的和尽可能大。你能帮帮她吗？

输入描述

第一行输入两个正整数n,m，代表矩阵的行数和列数。
第二行输入n个整数ai。
第三行输入m个整数bi。
1≤n,m≤105
−104≤ai,bi≤104

输出描述

一个整数，代表最终子矩形所有元素之和。

样例输入

3 3
1 0 1
1 -4 2

样例输出

4

提示

该矩阵为：

1 -4 2

0 0 0

1 -4 2 

最大元素之和的子矩阵为第三列的 1 到 3 行。元素和为 4。

样例2:

输入:

3 4

1 1 1

-1 -1 -1 -1

输出:

-1

提示:

矩阵为 3 行 4 列，每个元素都是 -1。因此任取一个 1*1 的子矩阵即可。

[提交][状态]
ACM算法攻关部