Problem 3B. RP++
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 3B. RP++
时间限制:0.5s
空间限制:64MB
题目背景
一天小季发现了一个刷题网站,点开这个网站的题库,发现一共有 \(n\) 道题目。在这个网站中,做对每道题目都可以获得一定的rp值;当然,这其中肯定有一些题目是小季不会做的,做这些题目不会让小季获得任何rp值(因为做不出来)。小季想从中选3道题目来做来获得尽可能高的rp值,不过选3道获得最高rp值的题目没有意思,小季想加点限制...
题目描述
以 \(x_1, x_2, x_3...,x_n\) 代表做每道题可以获得的rp值,\(y_1,y_2,y_3...,y_n\)代表每道题小季会不会做第 \(i\) 题,用 \(0\) 和 \(1\) 表示, \(0\) 代表不会做, \(1\) 代表会做;那么小季每道题可以获得的rp值就可以用 \(x_i * y_i\) 来表示。
现在小季要从中选出三道题 \(x_a, x_b, x_c\) ,满足以下条件:
- \(a < b < c\)
- \(x_a \le x_b \le x_c\)
小季想知道满足以上条件时最高可以获得的rp值,即你需要找到一个三元组 \([a,b,c]\) 在满足上述条件时 \(x_a*y_a + x_b * y_b + x_c * y_c\) 的值最大。
输入格式
输入包括三行,第一行一个整数 \(n\) ,代表题目数量;
第二行 \(n\) 个整数 \(x_1, x_2, x_3, .. , x_n\) 代表每道题可以获得的rp值;
第三行 \(n\) 个是 \(0\) 或 \(1\) 的整数 \(y_1, y_2, y_3, ..., y_n\) 代表对于每道题小季是否会做。
输出格式
输出一个整数,代表满足条件的可以获得的最大rp值。如果找不到满足条件的三元组,则输出 -1。
样例1
输入
6
10 20 30 40 50 10
0 0 1 1 0 1
输出
70
解释
选取第3,4,5道题获得的rp值是最高的。
样例2
输入
5
50 40 30 20 10
1 1 1 1 1
输出
-1
解释
不存在满足条件的三元组。
样例3
输入
3
10 20 30
0 0 0
输出
0
数据范围
对于 \(60\%\) 的数据,\(1 \le n \le 100\);
对于 \(100\%\) 的数据,\(1 \le n \le 2000\), \(0 \le x_i \le 100\).