Skip to content

14349: 【原4349】小测前夜

题目

题目描述

author: RebeccaPan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4349

Description

注意:本题可以使用的头文件仅限于cstdio iostream cstring

梦回高三,小艾想起了几个月前背诵高考古诗文篇目的时光……

已经是晚上了。第二天有小测,可是小艾还有$n$篇古诗文没有背。这$n$篇古诗文都有一个对应的瞌睡值$s_i(1 \leq i \leq n)$,也就是说,选择背诵篇目$i$会让小艾的瞌睡程度增加$s_i$。小艾目前的瞌睡程度已经是$t$,而当小艾的瞌睡程度$\geq k$时,小艾会直接睡到明早,那可就没有更多的时间背了!注意,因为背了一半的文章也是没背出来的文章,所以恰好让小艾瞌睡程度$\geq k$的那篇也视作没背的。

好在小测考到每个篇目的概率是一致的,所以为了小测分数更高,小艾只需要背诵尽可能多的文章即可。小艾预计,自己背了的篇目明日小测一定能默写对,没背的篇目有10%的概率瞎写对。小测只考察这n篇古诗词默写,每篇各一题,每题分值相同,小测满分为100。

“夜如何其?夜未艾。”时间不早了,小艾对明天的小测还有些紧张。请帮助小艾计算熬夜背书后,明日的小测期望最多能得多少分吧!

Input Format

输入共两行。

第1行为三个整数$n$,$t$,$k$,分别表示篇目数,小艾现在的瞌睡值,以及让小艾直接睡着的瞌睡值。

第2行为$n$个非负整数,表示这$n$篇古诗文的瞌睡值$s_i$。

Output Format

输出共一行。

第1行为一个整数$x$,表示小艾的期望最大分数(向下取整)。

Sample Input

5 0 10
2 4 6 10 1

Sample Output

64

共5道题,故每题20分。小艾最多能背诵三篇文章(瞌睡值为2 4 1),期望得分为$3 \times 20pt + 2 \times 10 \% \times 20pt = 64pt$

数据规模

对于40%的数据,

$1 \leq n \leq 5000, 0 \leq s_i \leq 1e7$

对于另外20%的数据,

$1 \leq n \leq 1e5, 0 \leq s_i \leq 1e7$

对于再另外40%的数据,

$1 \leq n \leq 1e6, 0 \leq s_i \leq 1e4$

对于全部数据,还有

$0 \leq t, k \leq 1e9$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!