Nerunun İtmiş Bağlantısı#12447

Nerunun İtmiş Bağlantısı

3 saniyə

256 meqabayt

Çətin

Neru internetdə videolara baxarkən bağlantısı qəflətən kəsildi. İndi o, çox əsəbidir və bağlantını mümkün qədər qeyri-sabit şəkildə bərpa etmək istəyir.

Bağlantı $n$ ardıcıl siqnal hüceyrəsindən ibarətdir. $k$ -cı hüceyrənin gücü $p_{k}$ p_k-ya bərabərdir.

Bağlantının qeyri-sabitliyi qonşu hüceyrələrdən asılıdır. Formal olaraq, bağlantının qiyməti belə müəyyən olunur:

$(p_{1} \oplus p_{2}) + (p_{2} \oplus p_{3}) + \dots + (p_{n - 1} \oplus p_{n})$ (p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).

Bağlantını bərpa etmək üçün Neru dəqiq iki başlanğıc mövqeyi $i$ və $j$ seçməlidir $(1 \leq i, j \leq n - 3)$ (1 \le i, j \le n-3). Hər seçilmiş mövqe üçün o, həmin mövqedən başlayan dörd ardıcıl hüceyrəni istənilən qaydada yenidən düzəldə bilər.

Başqa sözlə, Neru $p [i .. i + 3]$ p[i..i+3] və $p [j .. j + 3]$ p[j..j+3] parçalarının elementlərini müstəqil şəkildə yenidən düzəldə bilər.

Seçilmiş iki parça kəsişməməlidir, yəni $∣ i - j ∣ > 3$ |i-j| > 3 olmalıdır.

İki düzgün parça seçildikdən və onların elementləri optimal şəkildə yenidən düzəldildikdən sonra bağlantının mümkün maksimum qiymətini tapın.

Giriş

Birinci sətirdə bir tam ədəd $n$ $(8 \leq n \leq 2 \cdot 1 0^{5})$ (8 \le n \le 2 \cdot 10^5) — siqnal hüceyrələrinin sayı verilir.

İkinci sətirdə $n$ tam ədəd $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n $(0 \leq p_{i} < 2^{30})$ (0 \le p_i < 2^{30}) — siqnal hüceyrələrinin gücləri verilir.

Çıxış

Bir tam ədəd çıxarın — iki düzgün parça seçildikdən və onların elementləri optimal şəkildə yenidən düzəldildikdən sonra bağlantının mümkün maksimum qiyməti.

Nümunələr

Nümunə 1

Nümunə 2

Qeyd

Birinci nümunədə Neru $p [1..4]$ və $p [5..8]$ parçalarını seçə bilər.

Elementləri yenidən düzdükdən sonra massiv $[1, 2, 4, 3, 5, 6, 8, 7]$ [1, 2, 4, 3, 5, 6, 8, 7] ola bilər.

Bağlantının qiyməti belədir:

$(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54$ (1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

İkinci nümunədə optimal nəticələrdən biri $[5, 1, 12, 3, 10, 7, 9, 6, 15, 2]$ [5, 1, 12, 3, 10, 7, 9, 6, 15, 2] massividir və bağlantının qiyməti $105$ -ə bərabərdir.

Bal hesablama

Alt tapşırıq $1$ ( $10$ bal): $n = 8$ n = 8.
Alt tapşırıq $2$ ( $30$ bal): $8 \leq n \leq 40$ 8 \le n \le 40.
Alt tapşırıq $3$ ( $40$ bal): $8 \leq n \leq 4000$ 8 \le n \le 4000.
Alt tapşırıq $4$ ( $40$ bal): bütün $1 \leq i \leq n$ 1 \le i \le n üçün $0 \leq p_{i} \leq 1$ 0 \le p_i \le 1.
Alt tapşırıq $5$ ( $80$ bal): Əlavə məhdudiyyət yoxdur.