Editorial for VPEX P5 - Points Redistribution
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
For each query, solve the 0-1 knapsack with items between and
.
Key Concepts: Dynamic Programming
Time Complexity:
Subtask 2
Create a segment tree with each node storing the best value in range and
for every time
. Merge the nodes in range during query.
Key Concepts: Segment Tree, Dynamic Programming, Implementation
Time Complexity:
Subtask 3
It is possible to solve all queries from to
,
with 2 dp tables,
maximum value with weight
in the range
to
,
maximum with weight
from
to
. This table takes
to create. With a query from
to
,
for all
. This query takes
time.
Split the queries into groups:
,
. Sort both groups by
. Solve the queries with the method above using initially
, until a query is reached where
, then set
and repeat until all queries are solved.
Key Concepts: Offline Processing, Square Root Decomposition, Dynamic Programming, Implementation
Time Complexity:
Comments