問題一覧 > 通常問題

No.2478 Disjoint-Sparse-Table Optimization

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : nok0 / テスター : akakimidori りあん tsutaj beet 👑 tute7627 SPD_9X2 👑 rin204 だれ momoyuu KKT89
お気に入りにしたユーザー ProblemId : 10060 / 自分の提出
問題文最終更新日: 2023-09-17 20:46:38
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
Japan Alumni Group Summer Camp 2023 Day 2 (順位表) の他の問題:

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$.

  • $[L_i,R_i)\in S$
  • There exists an integer $x\ (L_i < x < R_i)$ such that $[L_i,x) \in S$ and $[x,R_i)\in S$
  • The cost of a set $S$ is defined as follows.

  • The sum of $A_l+A_{l+1}+\ldots+A_{r-1}$ over all intervals $[l,r)$ contained in $S$
  • Find the minimum cost of a set satisfying the conditions.

    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もしくは右上の雲マークをクリックしてアカウントを作成してください。