Masala #C21BP09POF

Xotira 256 MB Vaqt 2000 ms Qiyinchiligi 1 %

#Oson

#Game Theory

#Ochko'z algoritm

5.0 (Baholar 1)

Robotlar o'yini.

ravraS virtual o'yinlarni juda sevadi, va u ko'p vaqtlardan beri o'z o'yinini yaratish uchun harakat qilib yurgandi. Va yaratdi, o'yin sharti quyidagicha:

Sizga $n$ ta sondan iborat massiv beriladi. Massivdagi $i(1≤i≤n)$ -element, $i$ -robotning narxini bildiradi.
Har qanday robot qo'shni robotga urush e'lon qilishi mumkin(qoshni robot-o'ngdagi yoki chapdagi eng yaqin robot, agarda o'ngda yoki chapda robot bo'lsa).
Agar $X$ narxga ega robot, $Y$ narxga ega robotga urush e'lon qilsa, urush e'lon qilgan robot yutadi va uning narxi $X-Y$ ga aylanadi, yutqazgan robot esa yo'q bo'lib ketadi.
O'yinda yutish uchun faqat bitta robot qolishi va narxi maksimal bo'lishi shart.

ravraSning ukasi sirakeB ham virtual o'yinlarni juda yaxshi koradi va u bunaqa oyinni oynamay qolishi mumkin emas edi.

Ammo u bu oyinda yutishga juda qiynaliyapti, va sizdan yordam soramoqda.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n(1≤n≤10^6)$ -robotlar soni.

Ikkinchi qatorda $n$ ta butun son $aᵢ(-10^9≤aᵢ≤10^9)$ , $aᵢ$ - bu $i$ -robotning narxi.

Chiquvchi ma'lumotlar:

Bitta butun son - oxirgi robotning maksimal narxi.

Misollar

#	input.txt	output.txt
1	2 1 -2	3
2	3 -2 -1 1	4
3	4 2 2 -2 0	6

Izoh:

1-testta. 1-robot 2-robotga urush e'lon qiladi va o'yin tugaydi. Javob: 1-(-2)

2-testta. 2-robot 3-robotga urush e'lon qiladi. 2-robot narxi = -1-1 Robotlar narxi = [2,-2]. 1-robot 2-robotga urush e'lon qiladi. 1-robot narxi = 2-(-2). Robotlar narxi = [4]. O'yin tugaydi. Javob: 4.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin