TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3766
  • 問題
  • P3766 奶牛的歌声
    制限 : 時間制限 : - MS   メモリ制限 : 65536 KB
    審判説明 : 时限1000ms
    問題説明

    Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。
    每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。
    每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。
    一头奶牛听到的总音量为它听到的所有音量之和。
    自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。

    入力形式

    第1行:一个正整数N.

    第2到N+1行:每行包括2个用空格隔开的整数,分别代表站在队伍中第i个位置的奶牛的身高以及她唱歌时的音量.

    出力形式

    队伍中的奶牛所能听到的最高的总音量.

    サンプル入力 1

    3
    4 2
    3 5
    6 10

    サンプル出力 1

    7

    サンプル入力 2

    20
    12 16
    3 11
    10 14
    2 7
    16 5
    18 18
    14 18
    17 2
    1 8
    9 17
    6 13
    11 8
    20 14
    7 13
    13 11
    5 13
    19 11
    4 13
    15 9
    8 4

    サンプル出力 2

    63

    ヒント

    队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声,于是她能听到的总音量为2+5=7.虽然她唱歌时的音量为10,但并没有奶牛可以听见她的歌声.


    ソース  Usaco2006 Mar