A. 奶牛的歌声

    传统题 1000ms 256MiB

奶牛的歌声

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

输入

第一行: 一个整数 N.

接下来 N 行: 每行两个整数 hi,vih_i, v_i,分别代表站在队伍中第 i 个位置的奶牛的身高以及她唱歌时的音量.

输出

一个整数,表示能听到的最高的总音量.

样例输入

3
4 2
3 5
6 10

样例输出

7

样例解释

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

数据范围

1≤N≤5×104;1≤hi≤2×109;1≤vi≤1041 ≤ N ≤ 5×10^4;1 ≤ h_i ≤ 2×10^9;1 ≤ v_i ≤ 10^4

2026-10-15

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-15 7:40
结束于
2026-10-15 12:00
持续时间
4.3 小时
主持人
参赛人数
6