問題一覧 > 通常問題

No.2478 Disjoint-Sparse-Table Optimization

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : nok0nok0 / テスター : akakimidoriakakimidori りあんりあん tsutajtsutaj beetbeet 👑 tute7627tute7627 👑 SPD_9X2SPD_9X2 👑 rin204rin204 だれだれ momoyuumomoyuu KKT89KKT89
0 ProblemId : 10060 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-17 20:46:38

問題文

長さ $2Q - 1$ の整数列 $A$ 及び $Q$ 個の区間 $[L_i,R_i)$ が与えられます。ここで、$L_i,R_i$ は $L_i < R_i$ を満たし、かつ $1$ から $2Q$ までの整数がちょうど一個ずつ含まれます。

あなたの目標は、全ての $i=1,2,\ldots,Q$ について以下の条件の少なくとも一つを満たすような区間の集合 $S$ を作ることです。

  • $[L_i,R_i)\in S$
  • ある整数 $x\ (L_i < x < R_i)$ が存在して、$[L_i,x) \in S$ かつ $[x,R_i)\in S$

    • 集合 $S$ のコストは、以下で表されます。

  • $S$ に含まれる区間 $[l,r)$ 全てに対する、$A_l+A_{l+1}+\ldots+A_{r-1}$ の総和
    • 条件を満たす集合のコストの最小値を求めてください。

    制約

    • 入力は全て整数
    • $1 \le Q\le 100$
    • $1 \le L_i < R_i \le 2Q$
    • $L_1,\ldots,L_Q,R_1,\ldots,R_Q$ には $1$ から $2Q$ までの整数がちょうど一個ずつ含まれる
    • $1 \le A_i \le 10^9 $

    入力

    $Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$
$A_1$ $A_2$ $\ldots$ $A_{2Q-1}$

    出力

    最後に改行してください。

    サンプル

    サンプル1
    入力
    3
1 4
2 5
3 6
1 2 3 4 5
    出力
    20

    $S=\lbrace [1,4),[2,3),[3,5),[5,6)\rbrace$ とするのが最適で、この時のコストは $6 + 2 + 7 +5 = 20$ です。

    サンプル2
    入力
    5
3 7
1 10
5 9
4 8
2 6
6 4 8 5 9 8 9 8 2
    出力
    132

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。