P1901 发射站

    • 585通过
    • 1.1K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 单调队列 NOI导刊 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某地有 N 个能量发射站排成一行,每个发射站 i 都有不相同的高度 Hi,并能向两边(当 然两端的只能向一边)同时发射能量值为 Vi 的能量,并且发出的能量只被两边最近的且比 它高的发射站接收。

    显然,每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受,特别是为了安 全,每个发射站接收到的能量总和是我们很关心的问题。由于数据很多,现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。

    输入输出格式

    输入格式:

    第 1 行:一个整数 N;

    第 2 到 N+1 行:第 i+1 行有两个整数 Hi 和 Vi,表示第 i 个人发射站的高度和发射的能量值。

    输出格式:

    输出仅一行,表示接收最多能量的发射站接收到的能量值,答案不超过 longint。

    输入输出样例

    输入样例#1: 复制
    3
    4 2 
    3 5 
    6 10
    
    输出样例#1: 复制
    7

    说明

    对于 40%的数据,1<=N<=5000;1<=Hi<=100000;1<=Vi<=10000;

    对于 70%的数据,1<=N<=100000;1<=Hi<=2,000,000,000;1<=Vi<=10000;

    对于 100%的数据,1<=N<=1000000;1<=Hi<=2,000,000,000;1<=Vi<=10000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。