Решение задачи Скидки с Codeforces
Без пояснения   Просмотров: 80
Вы зашли в ближайший магазин, чтобы купить несколько плиток шоколада. В магазине продаются n плиток, i-я стоит ai монет (и вы хотите купить их все).
У вас есть m разных купонов, позволяющих покупать шоколадки на особых условиях. i-й купон позволяет купить qi шоколадок, при этом заплатив только за qi−1 наиболее дорогих из них (то есть самая дешевая из qi шоколадок вам достанется бесплатно).
Вы можете использовать только один купон; если вы используете купон i, вы должны выбрать qi шоколадок, которые вы купите по купону, а все остальные n−qi плиток вы купите без каких-либо скидок.
Чтобы понять, какой купон стоит использовать, вы хотите для каждого купона узнать, какое минимальное количество денег вам придется потратить, если вы используете его оптимально.
У вас есть m разных купонов, позволяющих покупать шоколадки на особых условиях. i-й купон позволяет купить qi шоколадок, при этом заплатив только за qi−1 наиболее дорогих из них (то есть самая дешевая из qi шоколадок вам достанется бесплатно).
Вы можете использовать только один купон; если вы используете купон i, вы должны выбрать qi шоколадок, которые вы купите по купону, а все остальные n−qi плиток вы купите без каких-либо скидок.
Чтобы понять, какой купон стоит использовать, вы хотите для каждого купона узнать, какое минимальное количество денег вам придется потратить, если вы используете его оптимально.