Colección de caramelos

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 4.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
C, C++, Java, Lua, Pascal, Python

Byteman está aquí en la tienda de golosinas para comprar caramelos para regalar a los niños. Hay \(n\) paquetes de caramelos en línea en un estante. El \(i^{th}\) paquete contiene \(V_i\) caramelos, y el \(i^{th}\) paquete tiene color \(T_i\). Byteman quiere comprar todos los paquetes de caramelos! pero el problema es que no tiene mucho dinero.

Byteman llevará todas los paquetes a casa usando cajas. Una caja contendrá una secuencia contigua de paquetes de caramelos (Nota: no confunda los paquetes con las cajas; las cajas contendrán paquetes y las paquetes contienen caramelos). Cada paquete pertenece exactamente a una caja. Byteman también es selecto acerca de los paquetes en una sola caja. Él no desea que dos paquetes en la misma caja tengan el mismo color. El costo de una caja es el OR a nivel de bit del número de caramelos en los paquetes que contiene. Por ejemplo, el costo de una caja que contiene tres paquetes, que contienen \(1, 2\) y \(3\) caramelos respectivamente, es 1 OR 2 OR 3 = 3.

¿Cuál es el costo total mínimo necesario para comprar todas los paquetes?

Entrada

La primera línea de entrada contiene a \(n\), el número de paquetes de caramelos. La segunda línea contiene \(n\) enteros separados por espacio, la \(i^{th}\) de las cuales representa a \(T_i\), el color del \(i^{th}\) paquete. La tercera línea contiene \(n\) enteros separados por espacio, el \(i^{th}\) de los cuales representa el número de caramelos \(V_i\) en el \(i^{th}\) paquetes de caramelos.

Restricciones

  • \(1 \leq n \leq 500000\)
  • \(1 \leq T_i \leq 10^6\)
  • \(0 \leq V_i \leq 10^6\)

Salida

Imprima un entereo simple el cual es la respuesta al problema planteado.

Ejemplo # 1 de Entrada

6
5 2 1 3 4 2
1000 0 1000 1 2 3

Ejemplo # 1 de Salida

1003

Byteman usara dos cajas. La primera caja contiene los tres primeros paquetes y tiene un costo de 1000 OR 0 OR 1000 = 1000. La segunda caja contiene los ultimos tres paquetes y tiene costo 1 OR 2 OR 3 = 3.

Ejemplo # 2 de Entrada

5
1 2 3 4 1
9 9 9 2 2

Ejemplo # 2 de Salida

11

Aqui Byteman usaria dos cajas. La primera caja contiene el primero, el segundo y el tercer paquete y tiene costo 9 OR 9 OR 9 = 9. La segunda caja contiene el cuarto y el quinto paquete y tiene costos 2 OR 2 = 2.


Comments

There are no comments at the moment.