P4480 [BJWC2018] Napkin Planning Problem

This problem is not the same as the Napkin Plan in the 24 Network Flow Problems.

A restaurant requires a varying number of napkins over $n$ consecutive days. Suppose on day $i$ ($i = 1, 2, \ldots, n$) it needs $r_i$ napkins. The restaurant can purchase new napkins at any time, at a cost of $p$ per napkin. Used napkins must be washed before reuse. Sending one used napkin to laundry A returns it after $m_1$ days at a cost of $c_1$; sending one used napkin to laundry B returns it after $m_2$ days at a cost of $c_2$. For example, a napkin used on day $k$ and sent to laundry A can be used on day $k+m_1$. Arrange the napkin usage plan over $n$ days to minimize the total cost.

The first line contains six positive integers $n, m_1, m_2, c_1, c_2, p$. The next $n$ lines each contain a positive integer $r_i$.

Output one line containing a single positive integer, the minimum total cost.

【Sample Explanation】 Day 1: Buy 8 napkins, costing 24. Send 2 napkins to laundry A and 6 napkins to laundry B. Day 2: Take back 2 napkins from laundry A, costing 4. Send 1 napkin to laundry B. Day 3: Take back 6 napkins from laundry B, costing 6. Day 4: Take back 1 napkin from laundry B, costing 1. This achieves the minimum cost. 【Constraints】 For 30% of the testdata, $1 \leq n \leq 5$, $1 \leq c_1, c_2, p \leq 5$, $1 \leq r_i \leq 5$. For 50% of the testdata, $1 \leq n \leq 100$, $1 \leq r_i \leq 50$. For 70% of the testdata, $1 \leq n \leq 5000$. For 100% of the testdata, $1 \leq n \leq 200000$, $1 \leq m_1, m_2 \leq n$, $1 \leq c_1, c_2, p \leq 100$, $1 \leq r_i \leq 100$. Translated by ChatGPT 5