Максимум#65

Максимум (Editorial)

Умова b_i \ge \max(a_i, a_{i+1}) рівносильна двом окремим нерівностям: a_i \le b_i та a_{i+1} \le b_i. Отже, кожне обмеження лише згори обмежує елементи , і різні елементи ніяк не пов'язані між собою.

Тому суму можна максимізувати покомпонентно: кожен a_j треба зробити якомога більшим, а це просто мінімум із усіх верхніх меж, що на нього накладаються.

На елемент a_j впливають ті b_i, у яких i = j або i = j - 1:

  • a_1 обмежує лише b_1, тому a_1 = b_1;

  • a_{n+1} обмежує лише b_n, тому a_{n+1} = b_n;

  • для 2 \le j \le n діють обидва обмеження, тому a_j = \min(b_{j-1}, b_j).

Відповідь — сума цих значень. Такий масив справді допустимий: кожна нерівність виконується за побудовою, а більшого значення жоден елемент прийняти не може.

Зверніть увагу на третій приклад в умові: нерівність нестрога, тому b_i може виявитися набагато більшим за фактичний максимум — це не помилка.

Складність — .