[eJOI2021] Waterfront
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
现有 丛初始高度为 的灌木。每丛灌木每天都会生长 的高度。
每天在灌木生长完毕后，园丁将对灌木剪枝 次。每次可以将任意一丛高度不小于 的灌木剪短 个单位。
求 天后最高的一丛灌木的高度的最小值。
输入格式
第一行四个正整数 。
接下来的 行，每行两个非负整数 。
输出格式
一个非负整数，表示 天后最高的一丛灌木的高度的最小值。
4 3 4 3
2 5
3 2
0 4
2 8
8
提示
样例解释
| 天数 | 灌木编号 | 高度变化量 |
|---|---|---|
| $2 \overset{+5}{\to} 7 \overset{-3}{\to} 4 \\ 3 \overset{+2}{\to} 5 \\ 0 \overset{+4}{\to} 4 \\ 2 \overset{+8}{\to} 10 \overset{-3}{\to} 7 \overset{-3}{\to} 4 \overset{-3}{\to} 1$ | ||
| $4 \overset{+5}{\to} 9 \overset{-3}{\to} 6 \overset{-3}{\to} 3 \\ 5 \overset{+2}{\to} 7 \\ 4 \overset{+4}{\to} 8 \\ 1 \overset{+8}{\to} 9 \overset{-3}{\to} 6 \overset{-3}{\to} 3$ | ||
| $3 \overset{+5}{\to} 8 \\ 7 \overset{+2}{\to} 9 \overset{-3}{\to} 6 \\ 8 \overset{+4}{\to} 12 \overset{-3}{\to} 9 \overset{-3}{\to} 6 \\ 3 \overset{+8}{\to} 11 \overset{-3}{\to} 8$ |
数据规模与约定
本题采用捆绑测试。
- Subtask 1（8 pts）：，，，。
- Subtask 2（22 pts）：。
- Subtask 3（43 pts）：。
- Subtask 4（27 pts）：。
对于 的数据，，，$0 \le \textit{height}_i,\textit{dailyGrowth}_i \le 10^4$。
说明
本题译自 eJOI2021 Day 2 C Waterfront。
妙妙题 eJOI蓝题
- Status
- Done
- Rule
- IOI
- Problem
- 13
- Start at
- 2024-11-2 9:15
- End at
- 2024-11-8 9:15
- Duration
- 144 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 25