bikeparking
Day2 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Uzbek (UZB)

B. Velosiped turargohi (Bike Parking)Problem Namebikeparking

Time Limit

1 second

Memory Limit

1 gigabyte

Sanne yaqinda ajoyib biznes g'oya o'ylab topdi: Eindhoven vokzalida premium velosipedturargohini (parkovkani) ijaraga berish. O'zining daromadini oshirish uchun, u turargohlarni N taturli guruhlarga ajratib chiqdi, ular 0 dan N − 1 gacha raqamlangan. 0-guruhdagi turargohvokzalga juda ham yaqin bo'lgani uchun ular premium turargoh hisoblanadi. Guruh raqamining
o'sib borishi turargohning yomonlashib borishini bildiradi. t-guruhdagi turargohda xt ta velosiped
qo'yish joylari bor.
Foydalanuvchilar

velosipedlarini

telefondasturiorqaliparkovkaqilishadi.

Harbirfoydalanuvchining o'z obuna darajasi bor va ular obuna darajalariga mos keluvchi guruhdan joy
berilishini xohlaydi. Ammo, xizmat ko'rsatish shartnomasida foydalanuvchilarga o'z darajasiga mosguruhdagi joyni ijaraga olishi kafolatlanmagan.
Agar s -darajali foydalanuvchiga t-guruhdagi to'xtash joyi berilsa, quyidagi uchta holatdan biri
sodir bo'ladi:
1. Agar t < s bo'lsa, foydalanuvchi xursand bo'ladi va dasturga yaxshi izoh qoldiradi.
2. Agar t = s bo'lsa, foydalanuvchi uchun bu qoniqarli bo'ladi va hech qanday izoh
qoldirmaydi.
3. Agar t > s bo'lsa, foydalanuvchi xafa bo'ladi va dasturga yomon izoh qoldiradi.
Hozirgi kunda, Sannening dasturida y0 + y1 + ... + yN −1 ta foydalanuvchi bor, bu yerda ys debobunasi bo'yicha s -darajadagi foydalanuvchilar soniga aytiladi. Siz Sannega to'xtash joylarini
ajratishga yordam berishingiz kerak. Har bir foydalanuvchi aynan bitta to'xtash joyini olishi kerak.
Hech qaysi to'xtash joyini bittadan ko'p odamga berish mumkin emas, lekin ba'zi to'xtash
joylaridan hech kim foydalanmasligi ham mumkin. Shuningdek, jami foydalanuvchilar soni jami
to'xtash joylari sonidan ko'p emas.
Sanne dasturining reytingini oshirmoqchi. Aytaylik, qoldirilgan yaxshi izohlar soni U , yomonizohlar soni D bo'lsin. Sizning vazifangiz U − D ning qiymatini maksimallashtirish.

Kiruvchi ma'lumotlar
bikeparking (1 of 4)

Birinchi qatorda N kiritiladi, guruh yoki darajalar soni.
Ikkinchi qatorda N ta butun son kiritiladi x0 , x1 , ..., xN −1 , har bir guruhdagi to'xtash joylari soni.
Uchinchi qatorda N ta butun son kiritiladi y0 , y1 , ..., yN −1 , har bir obuna darajasidagi
foydalanuvchilar soni.

Chiquvchi ma'lumotlar
Bitta butun son chiqaring, to'xtash joylari optimal ajratilganida U − D ning maksimal qiymati.

Cheklovlar va baholash
1 ≤ N ≤ 3 ⋅ 105 .
0 ≤ xi , yi ≤ 109 , barcha i = 0, 1, ..., N − 1 uchun.
y0 + y1 + ... + yN −1 ≤ x0 + x1 + ... + xN −1 ≤ 109 .
Yechimingiz bir-nechta test guruhlarida tekshiriladi. Har bir test guruhi uchun qanchadir ballberiladi. Barcha test guruhlarida bir-nechta testlar bor. Test guruhining ballini olish uchun
yechimingiz ushbu guruhdagi barcha testlarda to'g'ri ishlashi kerak.
GuruhBallCheklovlar

1

16

2

9

3

19xi , yi ≤ 1

424

N , xi , yi ≤ 100

532

Qo'shimcha cheklovlarsiz.

N = 2, xi ≤ 100, yi ≤ 100
xi = xj = yi = yj barcha i, j uchun. Boshqacha qilib aytganda x va y larningbarcha qiymatlari bir xil.

Namunalar
E'tibor bering, ba'zi namunalar barcha test guruhlariga mos tushmaydi. i -namuna i -test guruhiga
mos tushadi.
Birinchi misolda, Siz 0-darajadagi foydalanuvchiga 0-guruhdan to'xtash joyini berishingiz, ikkita 1darajadagi foydalanuvchilarga 0-guruhdan to'xtash joyini berishingiz (natijada 2ta yaxshi izoholasiz), va qolgan bitta 1-darajali foydalanuvchiga 1-guruhdan to'xtash joyini berishingiz mumkin.
Shunda reyting 2 ga teng bo'ladi.
Ikkinchi misolda, Siz 1-daraja foydalanuvchiga 0-guruhdan to'xtash joyini berishingiz, 2-daraja
foydalanuvchiga 1-guruhdan to'xtash joyini berishingiz, va 0-daraja foydalanuvchiga esa 2-bikeparking (2 of 4)

guruhdan to'xtash joyini berishingiz mumkin. Natijada Siz 2ta yaxshi va 1ta yomon izoh olasiz va
reyting 1ga teng bo'ladi.
Uchinchi misolda, Siz 1-daraja foydalanuvchiga 0-guruhdan to'xtash joyi, 0-daraja foydalanuvchiga
2-guruhdan to'xtash joyi, va 4-daraja foydalanuvchiga 3-guruhdan to'xtash joyi berishingiz
mumkin. Bu misolda ham 2ta yaxshi va 1ta yomon izoh olasiz va reyting 1ga teng bo'ladi.
To'rtinchi misol rasmda ko'rsatilgan. Siz 1-daraja foydalanuvchilariga 0-, 0-, 3- va 3-guruhdan
to'xtash joylarini berib, 2ta yaxshi va 2ta yomon izohlar olasiz. Keyin, 2-daraja foydalanuvchilariga
1-, 2-, 3- and 3-guruhdan to'xtash joylarini berib, 1ta yaxshi va 2ta yomon izoh olasiz. Natijada jami
3ta yaxshi izoh, 4ta yomon izoh bilan −1 reyting olasiz. Rasmda "Tier" – to'xtash joyining guruhini,"Level" foydalanuvchi darajasini bildiradi.

Beshinchi misolda, barchaga o'zining darajasidagi to'xtash joylarini berishingiz mumkin. Reyting 0ga teng bo'ladi.

bikeparking (3 of 4)

Input23 3Output

2

1 331

1 1 1
1 1 161

1 0 1 1 0 1
1 1 0 0 1 042 1 1 8-10 4 4 0101000000000
1000000000

bikeparking (4 of 4)