bikeparking
Day2 Tasks

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

Ukrainian (UKR)

B. Паркування велосипедівНазва задачіbikeparkingОбмеження часу1cОбмеження використання пам'яті

1024 MБВіка нещодавно придумала вигідну бізнес-ідею: здавати в оренду преміальні паркомісця длявелосипедів на залізничній станції Ейндховену. Щоб максимізувати прибуток, вона поділила
паркомісця для велосипедів на N різних типів, пронумерованих від 0 до N − 1. Паркомісця типу0 є преміальними, тому що розташовані дуже близько до платформ. Паркомісця з типами збільшими номерами є гіршими (чим більший номер типу паркомісця, тим гірше саме паркомісце).
Кількість паркомісць типу t дорівнює xt .
Ті, хто паркують свої велосипеди, отримують місце для паркування через мобільний додаток.
Кожен користувач має певний рівень підписки і очікує місце для паркування відповідного типу.
Однак поточні умови обслуговування не гарантують користувачам місце відповідного типу.
Якщо користувач з рівнем підписки s отримує місце для паркування типу t, тоді відбувається
одна з трьох речей:1. Якщо t < s , користувач буде задоволений і поставить додатку позитивну оцінку.
2. Якщо t = s , користувач буде задоволений, але не робитиме нічого.
3. Якщо t > s , користувач буде незадоволений і поставить додатку негативну оцінку.
Сьогодні у додатку Віки є y0 + y1 + ... + yN −1 користувачів, де ys — це кількість користувачів зрівнем підписки s . Вона потребує вашої допомоги в розподілі користувачів по паркомісцях.
Кожен користувач має отримати рівно одне місце. Жодне місце не може бути надано більш, ніжодному користувачу, але деякі паркомісця можуть залишатися незайнятими. Гарантується, щозагальна кількість користувачів не перевищує загальну кількість доступних паркомісць.
Віка хоче максимізувати рейтинг свого додатку. Нехай U — це кількість позитивних оцінок, а D —це кількість негативних оцінок додатку. Ваше завдання — максимізувати значення (U − D).

Формат вхідних данихУ першому рядку задано одне ціле число N — кількість різних типів паркомісць та рівнівпідписки.

bikeparking (1 of 4)У другому рядку задано N цілих чисел x0 , x1 , ..., xN −1 — кількості місць різних типів.
У третьому рядку задано N цілих чисел y0 , y1 , ..., yN −1 — кількості користувачів з різними
рівнями підписки.

Формат вихідних даних
Виведіть одне ціле число — максимально можливе значення (U − D), яке можна досягти
оптимальним розподілом користувачів по паркомісцях.

Обмеження та оцінювання1 ≤ N ≤ 3 ⋅ 105 .
0 ≤ xi , yi ≤ 109 для i = 0, 1, ..., N − 1.
y0 + y1 + ... + yN −1 ≤ x0 + x1 + ... + xN −1 ≤ 109 .
Ваше рішення буде протестоване на наборі підзадач, кожна з яких оцінюється в певну кількістьбалів. Кожна підзадача містить певний набір тестів. Щоб отримати бали за певну підзадачу, вамнеобхідно вирішити всі тести цієї підзадачі.
ПідзадачаБали

Обмеження

1162

93

19xi , yi ≤ 1

424N , xi , yi ≤ 100

532

Без додаткових обмежень.

N = 2, xi ≤ 100, yi ≤ 100
xi = xj = yi = yj для всіх i, j . Іншими словами, всі значення x та y увхідних даних однакові.

ПрикладиЗверніть увагу, що деякі з прикладів не є допустимим вхідними даними для всіх підзадач. i -йприклад допустимий принаймні для i -ї тестової групи.
У першому прикладі можна призначити користувача з рівнем підписки 0 на місце типу 0,призначити двох користувачів з рівнем 1 на місця типу 0 (отримуючи 2 позитивні оцінки), іпризначити іншого користувача з рівнем 1 на місце типу 1. Це дає рейтинг 2.
У другому прикладі можна призначити користувача з рівнем 1 на місце типу 0, користувача зрівнем 2 на місце типу 1, і користувача з рівнем 0 на місце типу 2. Це дає 2 позитивні оцінки і 1негативну оцінку, що призводить до рейтингу 1.

bikeparking (2 of 4)У третьому прикладі можна призначити користувача з рівнем 1 на місце типу 0, користувача зрівнем 0 на місце типу 2, і користувача з рівнем 4 на місце типу 3. Це дає 2 позитивні оцінки і 1негативну оцінку, що призводить до рейтингу 1.
Четвертий приклад проілюстровано нижче. Можна призначити користувачів з рівнем 1 на місця
типів 0, 0, 3 і 3, що дає 2 позитивні оцінки і 2 негативні оцінки. Потім призначити користувачів зрівнем 2 на місця типів 1, 2, 3 і 3, що дає 1 позитивну оцінку і 2 негативні оцінки. Загалом це дає 3позитивні оцінки і 4 негативні оцінки, отже, рейтинг становить −1.

У п'ятому прикладі можна призначити кожного на місце, що відповідає їхньому рівню підписки,таким чином рейтинг буде 0.

bikeparking (3 of 4)

Ввід

23 3

Вивід

2

1 3

3

1

1 1 1
1 1 161

1 0 1 1 0 1
1 1 0 0 1 04
2 1 1 8-1

0 4 4 0101000000000
1000000000

bikeparking (4 of 4)