Masala #YDGQVXRU0E
O'yin
Sizga \(2N\) ta karta berilgan bo'lib, ular bir qator qilib joylashtirilgan. Har bir kartada butun son yozilgan, bu sonlar ketma-ketlikda \(A_1, A_2, \dots, A_{2N}\)ko'rinishida berilgan.
Javlonbek va Ismoil navbatma-navbat yurish qiladigan o'yin o'ynashadi. O'yin quyidagi qoidalarga asoslanadi:
- Javlonbek navbati kelganda kartalar qatorining chap yoki o'ng chetidan bitta kartani tanlaydi va uning qiymatini o'z hisobiga qo'shadi. Tanlangan karta qatordan olib tashlanadi.
- Keyin Ismoil xuddi shu qoidalar asosida chap yoki o'ng chetidan bitta kartani tanlaydi va uning qiymatini o'z hisobiga qo'shadi.
- O'yin shu tartibda davom etadi va barcha kartalar tugaguniga qadar davom etadi.
O'yin tugaganidan so'ng, Javlonbekning olgan kartalar qiymatlari yig'indisi bilan Ismoilning olgan kartalar qiymatlari yig'indisi o'rtasidagi farqni maksimal qilishmoqchi. Ikkisi ham optimal o'ynaydi.
Birinchi qatorda kartalar soni N beriladi (ya'ni, qatorning uzunligi 2N). \((1≤N≤10^6)\)
Ikkinchi qatorda kartalarning qiymatlari \(A_1, A_2, \dots, A_{2N}\) lar beriladi. \((1≤A_i≤10^9)\)
Javlonbek va Ismoil kartalar yig'indisi o'rtasidagi maksimal farqni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 1 2 3 4 |
4 |
| 2 |
2 1 4 3 2 |
2 |
| 3 |
3 4 1 3 2 1 2 |
5 |
1-testda 2-testda
Birinchi 4 ni oladi Birinchi 2 ni oladi
Ikkinchi 1 ni oladi Ikkinchi 1 ni oladi
Birinchi 3 ni oladi Birinchi 4 ni oladi
Ikkinchi 2 ni oladi Ikkinchi 3 ni oladi
Demak, Demak,
4+3=7 2+4=6
1+2=3 1+3=4
7-3=4 ekan eng maksimal farq 6-4=2 ekan eng maksimal farq
Telegram kanalimizga obuna bo'ling