eolymp
bolt
Try our new interface for solving problems
Məsələlər

Maksimum cəm oyunu - rəqib altnəzarətçisi

Maksimum cəm oyunu - rəqib altnəzarətçisi

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

N sayda kartoçka soldan sağa yan-yana düzülmüşdür. Hər bir kartoçkada tam ədəd yazılmışdır. İki oyunçu nöbə ilə bir kartoçka götürür. Bu zaman yalnız ilk kartoçkanı, ya da son kartoçkanı götürmək olar. Bütün kartoçkalar götürüldükdən sonra oyun bitmiş sayılır (nə qədər ki, kartoçka var oyunçu mümkün gedişlərdən birini etməlidir). Oyunun məqsədi imkan daxilində ən böyük cəmi (götürülmüş kartoçkalardakı ədədlərin cəmini) əldə etməkdir.

Lakin aydın deyil, bu oyunu niyə tərs-rəis və yaltaq işçi oynayır. Tərs-rəis nəinki, öz gedişlərinə, hətta yaltaq işçinin də gedişlərinə tam və tamamilə nəzarət edə bilir. Tərs-rəis (hansı ki, ilk gedişi edir) hansı maksimal cəmi toplaya bilər?

Giriş verilənləri

İlk sətirdə kartoçkaların N (1N2013) sayı verilir. İkinci sətirdə boşluqla ayrılmış kartoçka üzərindəki N (modulca 10^3-ü aşmayan) ədəd verilir.

Çıxış verilənləri

İlk oyunçunun (tərs-rəisin) toplaya biləcəyi (hansı ki, buna zəmanət verilir) yeganə tam ədədi - maksimal cəmi verin.

Qeyd: Belə ki, tərs-rəis yaltaq işçinin gedişlərinə nəzarət etdiyi üçün, o ilk gedişdə 3 götürə və "rəqibinə" isə 1 götürmsəni əmr edə bilər.

Nümunə

Giriş verilənləri #1
4
1 2 9 3
Çıxış verilənləri #1
12
Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2