Moćni Niza

View as PDF

Submit solution


Points: 1
Time limit: 3.0s
Memory limit: 256M

Problem type

Dat je kružni niz A od n elemenata (elementi A_n i A_1 su susedni). Potrebno je podeliti niz u k podnizova susednih elemanta (svaki element se nalazi u tačno jednom podnizu) tako da se maksimizuje moć niza.

Moć niza definišemo kao bitwise AND snaga svih k izabranih podnizova. Snagu jednog podniza definišemo kao bitwise OR svih elemenata u tom podnizu.

U C++, operator bitwise AND ima oznaku \&, dok operator OR ima oznaku | (o bitwise operacijama)

Opis ulaza

  • Prva linija standardnog ulaza sadrži dva prirodna broja n i k (1 \leq k \leq n \leq 5 \cdot 10^5)
  • Druga linija standardnog ulaza sadrži n celih brojeva, niz A_i (0 \leq A_i \leq 10^9)

Opis izalza

U jednoj liniji standardnog izalza ispisati maksimalnu moć niza

Primer ulaza

6 3
2 2 2 4 4 4

Primer izalza

4

Objašnjenje primera

Optimalna podela niza u tri grupe je [2, 2, 4], [4], [4, 2]. (2 | 2 | 4) \& (4) \& (4 | 2) = 6 \& 6 \& 4 = 4


Comments

There are no comments at the moment.