Зверніть увагу, що після днів кількість доларів в автоматах буде повторюватися, тому необхідно знайти максимальне серед перших днів.
Для підзадачі 1 максимальна сума буде або після першого, або після другого дня, тому ми можемо просто вивести максимум між та n-sum(a).
Для підзадачі 2 достатньо змоделювати процес протягом перших днів і оновити максимум. Складність: O(n \cdot x)
Для підзадачі 3 зверніть увагу, що якщо жоден з автоматів не буде спорожнений, готівка зростає лінійно. Автомати будуть спорожнені не більше разів, тому ми можемо визначити ці моменти часу і змоделювати процес лише для цих моментів. Складність: O(n^2).
Для підзадачі 4 ми можемо змоделювати процес для кожного з днів, однак ми можемо підтримувати загальну суму доларів після кожного дня, використовуючи формули та кількість кожного a_i. Для цього, переходячи з дня до дня i+1, ми спочатку додаємо до загальної суми доларів, а потім віднімаємо для кожного автомата, який тепер містить доларів.
Для останньої підзадачі нам потрібно поєднати рішення з підзадач 3 та 4.