Ənənəvi Oyun#11730

Ənənəvi Oyun

2 saniyə

256 meqabayt

Çox çətin

Bir neçə il əvvəl, Chmyaaax hələ pis olmadıqda, o, Antonla Link-Cut planet sisteminin tayfalarından olan ənənəvi oyunu oynamağı sevirdi. Oyun $1 \times n$ 1 \times n lövhəsində baş verir, burada hər bir hüceyrədə $a_{i}, b_{i}$ a_i, b_i cüt ədədi var, bütün ədədlər fərqlidir. Həmçinin, başlanğıcda $1$ -ci mövqedə olan bir oyun parçası və başlanğıcda $0$ olan sehrli bir balans var. Oyunçular növbə ilə hərəkət edirlər, Chmyaaax birinci başlayır.

Tutaq ki, oyun parçası hazırda $i$ hüceyrəsindədir.

Chmyaaax növbəsində parçasını $k$ hüceyrə irəlilədə bilər, burada $k > 0$ k > 0, balansdan $k \cdot a_{i}$ k \cdot a_i qəpik çıxararaq, parçasının mövqeyini $i + k$ i + k-ə dəyişdirir.
Anton növbəsində parçasını $k$ hüceyrə geri apara bilər, burada $k > 0$ k > 0, balansa $k \cdot b_{i}$ k \cdot b_i qəpik əlavə edərək, parçasının mövqeyini $i - k$ i - k-ə dəyişdirir, ya da sehrdən istifadə edərək parçasını son hüceyrəyə aparır, balansı $(n - i) \cdot b_{i}$ (n - i) \cdot b_i qəpik artıraraq, parçasını $n$ mövqeyinə qoyur.

Hər hansı bir vaxtda, parça lövhədən kənara çıxa bilməz (yəni, onun mövqeyi $0$ -dan böyük və $n + 1$ n + 1-dən kiçik olmalıdır). Oyun parça $n$ hüceyrəsinə çatdıqda bitir. Chmyaaaxın məqsədi balansı maksimuma çatdırmaqdır, Antonun məqsədi isə balansı minimuma endirməkdir. Hər iki oyunçu optimal oynasa, oyunun sonunda balans nə olacaq? Bu şərtlər altında oyunun sonsuz davam etməyəcəyi sübut oluna bilər.

Giriş

Birinci sətir bir tam ədəd $n$ ( $2 \leq n \leq 1 0^{6}$ 2 \le n \le 10^6) — oyunun baş verdiyi lövhənin ölçüsünü ehtiva edir.

İkinci sətir $n$ tam ədəd $a_{i}$ a_i ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ -10^9 \le a_i \le 10^9) ehtiva edir.

Üçüncü sətir $n$ tam ədəd $b_{i}$ b_i ( $- 1 0^{9} \leq b_{i} \leq 1 0^{9})$ -10^9 \le b_i \le 10^9) ehtiva edir.

Hər bir $i$ və $j$ cütü üçün, belə ki, $i \neq = j$ i \neq j və $1 \leq i, j \leq n$ 1 \le i, j \le n, $a_{i} \neq = a_{j}$ a_i \neq a_j, $b_{i} \neq = b_{j}$ b_i \neq b_j, $a_{i} \neq = b_{j}$ a_i \neq b_j və hər bir $i$ ( $1 \leq i \leq n$ 1 \le i \le n) üçün $a_{i} \neq = b_{i}$ a_i \neq b_i şərtləri ödənilir.

Çıxış

Hər iki oyunçu optimal oynasa, oyunun sonunda balansın dəyərini çıxarmalısınız.

Nümunələr

Nümunə

Nümunə 1

Nümunə 2

Qeyd

Birinci test nümunəsində, Chmyaaax üçün optimaldır ki, başlanğıcdan sona qədər atlayaraq balansı $33 \cdot 7 = 231$ 33 \cdot 7 = 231 azaltsın, balansı $- 231$ əldə etsin. Onun üçün daha böyük balans əldə etməyə imkan verən heç bir strategiya olmadığı sübut oluna bilər.

İkinci test nümunəsində, Chmyaaax $2$ -ci hüceyrəyə atlayaraq balansı $- 5 \cdot 2 = - 10$ -5 \cdot 2 = -10 dəyişdirə bilər, Anton parçasını son hüceyrəyə apararaq balansı $15 \cdot 2 = 30$ 15 \cdot 2 = 30 artıraraq balansı $20$ edər.

Bal hesablama

( $25$ xal): $n \leq 20$ n \le 20;
( $30$ xal): $n \leq 50$ n \le 50, $- 200 \leq a_{i}, b_{i} \leq 200$ -200 \le a_i, b_i \le 200;
( $40$ xal): $n \leq 5000$ n \le 5000;
( $30$ xal): $n \leq 1 0^{5}$ n \le 10^5;
( $75$ xal): əlavə məhdudiyyət yoxdur.