bzoj#P1595. [Usaco2008 Jan]人工湖

[Usaco2008 Jan]人工湖

题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终,FJ 决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实,FJ 决定将湖的横截面建成 nn 个连续的平台高低错落的组合状,所有的平台从左到右按 11nn 依次编号。当然咯,在湖中注入水后,这些平台都将被淹没。

平台i在设计图上用它的宽度 wiw_i 和高度(你可以理解为该平台顶离约翰挖的地基的高度)hih_i 来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张约翰的设计图:

按 FJ 的设想,在坑挖好后,他会以 11 单位每分钟的速度往最低的那个平台上注水。水在离开水管后立即下落,直到撞到平台顶或是更早些时候注入的水然后,与所有常温下的水一样,它会迅速地流动、扩散。简单起见,你可以认为这些都是在瞬间完成的。FJ 想知道,对于每一个平台,它的顶部是从哪个时刻开始,与水面的距离至少为 11 单位长度。

注意:数据不保证答案全部在32位整型变量的范围内

输入格式

  • 11 行:11 个整数 nn

  • 2n+12\sim n+1 行:第 i+1i+1 行为 22 个用空格隔开的整数 wiw_ihih_i,描述了第 ii 个平台

输出格式

  • 1n1\sim n 行:第 ii 行为 11 个整数,表示平台 ii 的顶到水面的距离从何时开始大于 11 单位长度
3
4 2
2 7
6 4
4
50
26

数据规模与约定

对于 100%100\% 的数据,1n1051\leq n\leq 10^51wi10001\leq w_i\leq 10001hi1061\leq h_i\leq 10^6

提示

输入对应了题目中给出的例子,一共有 33 个平台,FJ 选定的注水点在最低的 11 号平台上方。

44 分钟后平台 11 被淹没。2626 分钟后平台 33 被淹没。5050 分钟后平台 22 被淹没。

题目来源

Usaco2008 Jan Gold