问题1930--【中级】摩天飞轮

1930: 【中级】摩天飞轮

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

你正在经营一座摩天轮,该摩天轮共有 4 个座舱 ,每个座舱 最多可以容纳 4 位游客 。

你可以旋转座舱,但每次旋转都需要支付一定的运行成本 R 。摩天轮每次旋转都恰好转动 1 / 4 周。 给你一个长度为 n 的数组 C , C[i] 是在第 i 次旋转之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i - 1 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 B ,一旦该座舱再次抵达地面,他们就会离开座舱结束游玩。 你可以随时停下摩天轮,即便是 在服务所有游客之前 。如果你决定停止运营摩天轮,为了保证所有游客安全着陆,将免费进行所有后续轮转 。

注意,如果有超过 4 位游客在等摩天轮,那么只有 4 位游客可以登上摩天轮,其余的需要等待 下一次轮转 。 

输出最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案,则返回 -1 。

输入

第一行,三个整数 n , B, R。 第二行, n 个正整数,表示每一轮排队的顾客数量。

输出

一个整数,表示收益最高时的转动次数,如果收益一直为非正数,输出 -1。

样例输入 Copy

2 5 6
8 3 

样例输出 Copy

3

提示

1 <= n <= 105 

0 <= C[i] <= 50 

1 <= B, R <= 100

来源/分类

模拟