No.2478 Disjoint-Sparse-Table Optimization
問題文最終更新日: 2023-09-17 20:46:38
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
You are given an integer sequence $A$ of length $2Q - 1$ and $Q$ intervals $[L_i,R_i)$. Here, $L_i,R_i$ satisfy $L_i < R_i$, and each integer from $1$ to $2Q$ appears exactly once among them.
Your goal is to construct a set $S$ of intervals such that at least one of the following conditions holds for every $i=1,2,\ldots,Q$.
The cost of a set $S$ is defined as follows.
Constraints
- All input values are integers
- $1 \le Q\le 100$
- $1 \le L_i < R_i \le 2Q$
- Each integer from $1$ to $2Q$ appears exactly once among $L_1,\ldots,L_Q,R_1,\ldots,R_Q$
- $1 \le A_i \le 10^9 $
Input
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$
$A_1$ $A_2$ $\ldots$ $A_{2Q-1}$
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 4 2 5 3 6 1 2 3 4 5
Output
20
It is optimal to take $S=\lbrace [1,4),[2,3),[3,5),[5,6)\rbrace$, and the cost in this case is $6 + 2 + 7 +5 = 20$.
Sample 2
Input
5 3 7 1 10 5 9 4 8 2 6 6 4 8 5 9 8 9 8 2
Output
132
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nok0
akakimidori
りあん
tsutaj
beet
tute7627
SPD_9X2
だれ
momoyuu