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\).

2023秋 悬赏令第三周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-22 18:30
结束于
2023-10-29 00:00
持续时间
149.5 小时
主持人
参赛人数
85