問題一覧 > 通常問題

No.2478 Disjoint-Sparse-Table Optimization

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : nok0 / テスター : akakimidori りあん tsutaj beet 👑 tute7627 👑 SPD_9X2 👑 rin204 だれ momoyuu KKT89
0 ProblemId : 10060 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-17 20:46:38

問題文

長さ 2Q−12Q - 1 の整数列 AA 及び QQ 個の区間 [Li,Ri)[L_i,R_i) が与えられます。ここで、Li,RiL_i,R_i は Li<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+…+Ar−1A_l+A_{l+1}+\ldots+A_{r-1} の総和
    • 条件を満たす集合のコストの最小値を求めてください。

    制約

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

    入力

    QQ
L1L_1 R1R_1
⋮\vdots
LQL_Q RQR_Q
A1A_1 A2A_2 …\ldots A2Q−1A_{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もしくは右上の雲マークをクリックしてアカウントを作成してください。