Codeforces Round 920 (Div. 3) |
---|
Закончено |
Степан — очень занятой человек, сегодня ему нужно отправить $$$n$$$ сообщений в моменты времени $$$m_1, m_2, \dots m_n$$$ ($$$m_i < m_{i + 1}$$$). Но, к сожалению, к моменту времени $$$0$$$ на его телефоне осталось всего $$$f$$$ единиц заряда. В момент времени $$$0$$$ телефон включен.
За одну единицу времени включенный телефон теряет $$$a$$$ единиц заряда. Также в любой момент времени Степан может выключить телефон и включить его позже. Это действие израсходует $$$b$$$ единиц энергии за раз. Считайте включение и выключение моментальным, то есть вы можете включить его в момент $$$x$$$ и послать сообщение в тот же момент и наоборот, послать сообщение в момент $$$x$$$ и выключить телефон в тот же момент.
Если в какой-то момент уровень заряда опускается до $$$0$$$ (становится $$$\le 0$$$), то отправить сообщение в этот момент времени невозможно.
Так как все сообщения очень важны для Степана, он хочет узнать, сможет ли он отправить все сообщения, без возможности зарядить телефон.
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания наборов.
Первая строка каждого набора содержит четыре целых числа $$$n$$$, $$$f$$$, $$$a$$$ и $$$b$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le f, a, b \le 10^9$$$) — количество сообщений, изначальный заряд телефона, расход заряда за единицу времени и расход при последовательном выключении и включении.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$m_1, m_2, \dots, m_n$$$ ($$$1 \le m_i \le 10^9$$$, $$$m_i < m_{i + 1}$$$) — моменты времени, в которые нужно отправить сообщения.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если Степан сможет отправить все сообщения и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
61 3 1 537 21 1 34 6 10 13 17 20 265 10 1 21 2 3 4 51 1000000000 1000000000 100000000010000000003 11 9 66 8 1012 621526648 2585904 356629951789 61859 71998 73401 247675 298086 606959 663464 735972 806043 806459 919683
NO YES YES NO NO YES
В первом наборе входных данных примера в момент времени $$$0$$$ заряд телефона равен $$$3$$$. При отправке сообщения в момент времени $$$3$$$ без выключения будет потрачено $$$(3 - 0) \cdot 1 = 3$$$ единицы заряда, в таком случае заряд упадёт до $$$0$$$ и Степан не сможет отправить это сообщение. При выключении и включении заряд телефона уменьшится на $$$5$$$, а значит и таким образом отправить сообщение не получится.
Во третьем наборе входных данных примера в момент времени $$$0$$$ заряд телефона равен $$$10$$$, за одну единицу времени телефон теряет $$$1$$$ единицу заряда, а при выключении и включении — $$$2$$$ единицы заряда. Чтобы отправить все сообщения можно действовать следующим образом:
Последний (шестой) набор примера может упасть, если в вашем решении есть переполнение целочисленного типа.
Название |
---|