Problem description

Back
Show PDF
BitBeat
(A)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

BitBeat to rytmiczna gra komputerowa, w której gracz układa sekwencje dźwięków. Do dyspozycji ma N dźwięków ponumerowanych liczbami od 1 do N. Musi ułożyć z nich utwór rytmiczny, a zarazem nowatorski i różnorodny pod względem użytych tonów.

Każdy dźwięk ma przypisane dwie liczby: dla i-tego dźwięku są to Ai oraz Bi. Oznaczają one odpowiednio jego wysokość i punktację. Powiemy, że ciąg dźwięków d1, …, dk jest rytmiczny, jeśli Adi XOR1 Adi + 1> max(Adi, Adi + 1) dla każdego i < k. Gracz dostaje punkty za różne2 dźwięki występujące w ciągu. Konkretnie, jeśli w ciągu pojawia się dźwięk x, to gracz dodaje do swojego wyniku liczbę Bx. Za kolejne wystąpienia tego samego dźwięku nie otrzymuje dodatkowych punktów.

Jaś, który dostał tę wspaniałą grę za darmo na Epicu, zastanawia się teraz, od jakiego dźwięku powinien rozpocząć swój ciąg rytmiczny. Pomóż mu i napisz program, który dla każdego i od 1 do N wypisze maksymalną liczbę punktów, jaką może uzyskać, rozpoczynając swój ciąg od dźwięku i.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę dźwięków.

W drugim wierszu wejścia znajduje się N liczb całkowitych Ai, oddzielonych pojedynczymi odstępami, będących wysokościami kolejnych dźwięków.

W trzecim wierszu wejścia znajduje się N liczb całkowitych Bi, oddzielonych pojedynczymi odstępami, będących punktacją za kolejne dźwięki.

Wyjście

Wyjście powinno składać się z N linii.

W i-tej z nich powinna znaleźć się maksymalna liczba punktów możliwa do uzyskania z ciągu rytmicznego rozpoczynającego się od dźwięku i.

Ograniczenia

1 ≤ N ≤ 100 000.
1 ≤ Ai ≤ 230 − 1.
1 ≤ Bi ≤ 109.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 200 13
2 N ≤ 2000 18
3 A1 = A2 = … = An 4
4 Liczby Ai są potęgami dwójki. 7
5 Ai ≤ 212 − 1 19
6 Bez dodatkowych ograniczeń 39

Przykład

Wejście Wyjście Wyjaśnienie 
3
2 1 1
20 30 10

60
60
60

W tym przykładzie rytmiczne ciągi to dokładnie takie, w których dźwięk 1 może sąsiadować z dźwiękiem 2 (bo 2 XOR 1 = 3 > max(2, 1) = 2), oraz dźwięk 1 może sąsiadować z dźwiękiem 3 (z tego samego powodu). Dźwięk 2 nie może sąsiadować z dźwiękiem 3, bo 1 XOR 1 = 0 < 1. Ciągi maksymalizujące wynik to np: 1213, 213, 312. Ciągi te zawierają wszystkie dźwięki, więc dają maksymalny wynik.
Wejście Wyjście Wyjaśnienie 
4
5 4 4 5
10 20 30 40

10
20
30
40

W tym przykładzie nie istnieją rytmiczne ciągi o długości większej niż jeden.
Wejście Wyjście 
5
1 2 1 7 11
20 10 30 100 100

60
60
60
200
200

  1. Operacja XOR jest opisana tutaj: XOR Wikipedia. W C++ i Pythonie symbol operacji XOR to ^.↩︎

  2. Dźwięki są różne, jeśli są oznaczone różnymi liczbami. Różne dźwięki mogą mieć tę samą wysokość oraz punktację.↩︎