煜拿到了一个n行m列的矩阵，矩阵中每个元素的权值由a数组和b数组决定。第ii行第jj列的元素为ai∗bj。
煜希望选择一个子矩形，使得该子矩形所有元素的和尽可能大。你能帮帮她吗？
问题 H: 煜的子矩形
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 3
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行输入两个正整数n,m，代表矩阵的行数和列数。
第二行输入n个整数ai。
第三行输入m个整数bi。
1≤n,m≤105
−104≤ai,bi≤104
第二行输入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 的子矩阵即可。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版