← 返回题目列表

Codeforces · 774/A

A. 游乐园

中文机器翻译题面 查看原题

学生决定去游乐园。其中一些人与父母在一起。总共有 n 个人来到公​​园,他们都想到达最极限的景点并在上面滚一次。

景点出售x人团体门票,每组至少须有一名成人(也有可能团体由一名成人组成)。该团体的票价为c1 + c2·(x - 1)2(特别是,如果该团体由一个人组成,则价格为c1)。

所有来公园的学生和家长决定分成几组,每个游客都只参加一组,并且参观最极限景点的总费用尽可能低。您需要确定这个最低可能总价。每组中至少应有一名成人。

输入

第一行包含三个整数 n、c1 和 c2 (1 ≤ n ≤ 200 000, 1 ≤ c1, c2 ≤ 107) - 游客数量和用于确定团体票价的参数。

第二行包含长度为 n 的字符串,由 0 和 1 组成。如果字符串的第 i 个符号为零,则第 i 个访客是学生,否则第 i 个访客是成年人。保证至少有一名成人。可能没有学生。

输出

打印所有学生及其家长参观最极限景点的最低价格。他们每个人都应该在景点上滚动一次。

示例

输入 #1

3 4 1
011

输出 #1

8

输入 #2

4 7 2
1101

输出 #2

18

注意

在第一个测试中,一组三人应该去景点。那么他们必须支付 4 + 1 * (3 - 1)2 = 8。

第二次测试时最好分两组去景点。第一组应由两名成人(例如第一人和第二人)组成,第二组应由一名学生和一名成人(第三人和第四人)组成。那么每组人数为两人,每组门票价格为 7 + 2 * (2 - 1)2 = 9。因此,两组的总价格为 18。