3257: 凸型区域
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：8
题目描述
给定一个 2*n 的长方形网格，请从中找出一片凸型的区域，使得这片区域的分数之和达到最大。以下是一个例子，黑框表示分数最大的凸型区域:
给定 u1,u2,··,un以及 d,d2,…·,dn，请找到四个下标满足
1<i<x<y<j≤n使得ux + ux+1+···+uy+di+di+1+·..+dj达到最大。
输入
第一行:单个正整数表示 n。
第二行:n 个整数表示 u1,u2,···,un。
第三行:n 个整数表示 d,d2,···,dn。
输出
单个整数：表示凸型区域的最大分数之和。
。对于 25% 的分数& 5 lt;n< 100;
。对于 50% 的分数& 5 lt;n< 1000;
。对于 75% 的分数& 5 lt;n< 10000
。对于 100% 的分数& 5 lt;n< 100000
-10000 ≤ ui ≤ 10000
-10000< di < 10000
。对于 25% 的分数& 5 lt;n< 100;
。对于 50% 的分数& 5 lt;n< 1000;
。对于 75% 的分数& 5 lt;n< 10000
。对于 100% 的分数& 5 lt;n< 100000
-10000 ≤ ui ≤ 10000
-10000< di < 10000
样例输入 复制
10
8 9 -6 -8 3 -1 4 -3 10 -7
-4 -10 -5 1 5 6 -2 7 -9 2样例输出 复制
23