P10769 「CROI · R2」Bus Shuttle

City H is a metropolis with heavy passenger traffic. To facilitate suburban travel, the city built a suburban railway parallel to the main highway. There are several transfer stations where both trains and buses stop. Currently, the railway operates one-way trains only during morning and evening rush hours.  The figure shows transfer stations (blue arrows) where railway passengers can switch to buses. We focus only on transfer stations in this problem.

To handle peak-hour crowds, the bus company will deploy $k$ buses along a route with $n$ transfer stations (numbered 1 to $n$ west-to-east). Each transfer station $i$ has a priority value $v_i$. The travel time from station $i$ to $i+1$ is $s_i$ (ignoring stop time). The railway arrives at station $i$ at time $t_i$. Bus travel time between stations is always ≥ railway travel time. You must schedule $k$ buses such that: 1. All passengers arriving at any station $i$ at $t_i$ can board a bus (bus arrival time ≥ $t_i$). 2. For each station $i$, the **dissatisfaction** is calculated as: (waiting time for the first bus) × (priority $v_j$ of the bus's origin station). If multiple buses arrive simultaneously, passengers choose the one with the smallest $v_j$. Minimize the total dissatisfaction across all stations for multiple queries with different $t_i$ and $k$.

N/A

N/A

**【Data Range】** Constraints: - $1 \leq n \leq 1000$, $1 \leq p \leq 10$ - $s_i \geq t_{i+1} - t_i \geq 0$ - $1 \leq q_i, k_i \leq 10^6$, $0 \leq v_i, \sum s_i \leq 10^6$, $1 \leq t_i \leq 2 \times 10^6$ **Subtasks:** | Subtask | $n$ | $q$ | $k_i$ | $\sum s_i$ | Special | Points | |---------|-----|-----|-------|------------|---------|--------| | 1 | 15 | 1e3 | 1e3 | 15 | None | 5 | | 2 | 15 | 1e6 | 1e6 | 1e6 | None | 5 | | 3 | 100 | 1e6 | 1e6 | 1e6 | None | 15 | | 4 | 1e3 | 1e6 | 1e6 | 1e6 | A | 5 | | 5 | 1e3 | 1e6 | 1e6 | 1e6 | B | 30 | | 6 | 1e3 | 1e3 | 1.1e3 | 1e3 | None | 10 | | 7 | 1e3 | 1e6 | 1e6 | 1e6 | None | 30 | - **Special A**: $s_i = t_{i+1} - t_i$ - **Special B**: $v_i = 1$ **【Sample Explanation】** Below are feasible optimal bus scheduling plans for the sample queries. Note that there may be multiple valid optimal solutions. **For the first schedule in Sample 1:** - **When $ k=1 $:** A bus departs station 1 at time $ 1 $. Operational details: | | Station 1 | Station 2 | Station 3 | | :-------------------: | :-------: | :-------: | :-------: | | Railway Arrival Time | $ 1 $ | $ 3 $ | $ 7 $ | | Bus Service 1 Arrival | $ 1 $ | $ 4 $ | $ 8 $ | | Boarded Service | Service 1 | Service 1 | Service 1 | | Waiting Time | $ 0 $ | $ 1 $ | $ 1 $ | Service 1 starts at station 1 ($ v_1=6 $). Total dissatisfaction: $$ 6 \times 0 + 6 \times 1 + 6 \times 1 = 12 $$ - **When $ k=2 $:** Buses depart station 1 at $ t=1 $ and station 2 at $ t=3 $. Operational details: | | Station 1 | Station 2 | Station 3 | | :-------------------: | :-------: | :-------: | :-------: | | Railway Arrival Time | $ 1 $ | $ 3 $ | $ 7 $ | | Bus Service 1 Arrival | $ 1 $ | $ 4 $ | $ 8 $ | | Bus Service 2 Arrival | — | $ 3 $ | $ 7 $ | | Boarded Service | Service 1 | Service 2 | Service 2 | | Waiting Time | $ 0 $ | $ 0 $ | $ 0 $ | Service 1 starts at station 1 ($ v_1=6 $), Service 2 at station 2 ($ v_2=2 $). Total dissatisfaction: $$ 6 \times 0 + 2 \times 0 + 2 \times 0 = 0 $$ **For the second schedule in Sample 1:** - **When $ k=1 $:** A bus departs station 1 at $ t=2 $. Operational details: | | Station 1 | Station 2 | Station 3 | | :-------------------: | :-------: | :-------: | :-------: | | Railway Arrival Time | $ 2 $ | $ 3 $ | $ 5 $ | | Bus Service 1 Arrival | $ 2 $ | $ 5 $ | $ 9 $ | | Boarded Service | Service 1 | Service 1 | Service 1 | | Waiting Time | $ 0 $ | $ 2 $ | $ 4 $ | Total dissatisfaction: $$ 6 \times 0 + 6 \times 2 + 6 \times 4 = 36 $$ - **When $ k=2 $:** Buses depart station 1 at $ t=2 $ and station 2 at $ t=3 $. Operational details: | | Station 1 | Station 2 | Station 3 | | :-------------------: | :-------: | :-------: | :-------: | | Railway Arrival Time | $ 2 $ | $ 3 $ | $ 5 $ | | Bus Service 1 Arrival | $ 2 $ | $ 5 $ | $ 9 $ | | Bus Service 2 Arrival | — | $ 3 $ | $ 7 $ | | Boarded Service | Service 1 | Service 2 | Service 2 | | Waiting Time | $ 0 $ | $ 0 $ | $ 2 $ | Total dissatisfaction: $$ 6 \times 0 + 2 \times 0 + 2 \times 2 = 4 $$ - **When $ k=4 $:** Buses depart: - Station 1 at $ t=-2 $ and $ t=2 $. - Station 2 at $ t=1 $ and $ t=3 $. Operational details: | | Station 1 | Station 2 | Station 3 | | :-------------------: | :-------: | :-------: | :-------: | | Railway Arrival Time | $ 2 $ | $ 3 $ | $ 5 $ | | Bus Service 1 Arrival | $-2$ | $ 1 $ | $ 5 $ | | Bus Service 2 Arrival | $ 2 $ | $ 5 $ | $ 9 $ | | Bus Service 3 Arrival | - | $ 1 $ | $ 5 $ | | Bus Service 4 Arrival | - | $ 3 $ | $ 7 $ | | Boarded Service | Service 2 | Service 4 | Service 3 | | Waiting Time | $ 0 $ | $ 0 $ | $ 0 $ | Services 1/2 start at station 1 ($ v_1=6 $), Services 3/4 at station 2 ($ v_2=2 $). Total dissatisfaction: $$ 6 \times 0 + 2 \times 0 + 2 \times 0 = 0 $$ **Note:** At Station 3, Services 1 and 3 arrive simultaneously at $ t=5 $. Passengers choose Service 3 (lower $ v_j=2 $) over Service 1 ($ v_j=6 $).