[eJOI 2021] Waterfront

ID: 7231

远端评测题

1000ms

512MiB

难度: 5

上传者:

标签>

2021

eJOI

题目描述

现有 $N$ 丛初始高度为 $\textit{height}_i$ 的灌木。每丛灌木每天都会生长 $\textit{dailyGrowth}_i$ 的高度。

每天在灌木生长完毕后，园丁将对灌木剪枝 $k$ 次。每次可以将任意一丛高度不小于 $x$ 的灌木剪短 $x$ 个单位。

求 $M$ 天后最高的一丛灌木的高度的最小值。

第一行四个正整数 $N,M,k,x$ 。

接下来的 $N$ 行，每行两个非负整数 $\textit{height}_i,\textit{dailyGrowth}_i$ 。

一个非负整数，表示 $M$ 天后最高的一丛灌木的高度的最小值。

天数	灌木编号	高度变化量
$1$	$1 \\ 2 \\ 3 \\ 4$	$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$
$2$		$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$		$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）： $1 \le N \le 100$ ， $M=k=x=1$ ， $\textit{height}_i \ge 1$ ， $\textit{dailyGrowth}_i=0$ 。
Subtask 2（22 pts）： $1 \le N,M \le 500$ 。
Subtask 3（43 pts）： $1 \le N,M \le 5000$ 。
Subtask 4（27 pts）： $1 \le N,M \le 10^4$ 。

对于 $100\%$ 的数据， $1 \le k \le 1000$ ， $1 \le x \le 10^4$ ， $0 \le \textit{height}_i,\textit{dailyGrowth}_i \le 10^4$ 。

本题译自 eJOI2021 Day 2 C Waterfront。