問題一覧 > 通常問題

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

問題文

長さ 2Q12Q - 1 の整数列 AA 及び QQ 個の区間 [Li,Ri)[L_i,R_i) が与えられます。ここで、Li,RiL_i,R_iLi<RiL_i < R_i を満たし、かつ 11 から 2Q2Q までの整数がちょうど一個ずつ含まれます。

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

  • [Li,Ri)S[L_i,R_i)\in S
  • ある整数 x (Li<x<Ri)x\ (L_i < x < R_i) が存在して、[Li,x)S[L_i,x) \in S かつ [x,Ri)S[x,R_i)\in S
  • 集合 SS のコストは、以下で表されます。

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

    制約

    • 入力は全て整数
    • 1Q1001 \le Q\le 100
    • 1Li<Ri2Q1 \le L_i < R_i \le 2Q
    • L1,,LQ,R1,,RQL_1,\ldots,L_Q,R_1,\ldots,R_Q には 11 から 2Q2Q までの整数がちょうど一個ずつ含まれる
    • 1Ai1091 \le A_i \le 10^9

    入力

    QQ
    L1L_1 R1R_1
    \vdots
    LQL_Q RQR_Q
    A1A_1 A2A_2 \ldots A2Q1A_{2Q-1}
    

    出力

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

    サンプル

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

    S={[1,4),[2,3),[3,5),[5,6)}S=\lbrace [1,4),[2,3),[3,5),[5,6)\rbrace とするのが最適で、この時のコストは 6+2+7+5=206 + 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もしくは右上の雲マークをクリックしてアカウントを作成してください。