2731：凸型区域的最大值
时间限制：2 S / 内存限制：65536 KB
AC：8 / Submit：17
| 问题描述 |
|---|
给定一个$$2$$行$$n$$列的长方形网格，请从中找出一片凸型的区域，使得这片区域的分数之和达到最大。 以下是一个例子，黑框表示分数最大的凸型区域。
形式化的表示：若凸型区域的第一行的左右端点为$$a,b$$，第二行的左右端点为$$c,d$$，那么必须满足：$$1 \le c \lt a \le b \lt d \le n$$。 |
| 输入描述 |
第一行是一个正整数$$n$$表示列数。（$$3 \le n \le 10^5$$） 接下来一行$$n$$个整数分别表示$$u_i$$。（$$-10^4 \le u_i \le 10^4$$） 最后一行$$n$$个整数分别表示$$d_i$$。（$$-10^4 \le d_i \le 10^4$$） |
| 输出描述 |
在一行中输出凸型区域的最大值。 |
| 样例输入复制样例 |
10 8 9 -6 -8 3 -1 4 -3 10 -7 -4 -10 -5 1 5 6 -2 7 -9 2 |
| 样例输出 |
23 |
| 相关 |
