‹ 上一题 下一题 ›

s09192. 冷却期 未做

1000 ms 256 MB 测试点 10 通过率 33% S-06·贪心进阶与反悔贪心反悔堆

题目描述

自动柜台按轮次处理订单,共 轮,第 轮到来一份报酬为 的订单。柜台维护一个已接订单集合,集合大小不能超过容量 。每一轮按下列规则运行:

  1. 若柜台处于冷却期,本轮订单被系统直接跳过(不接单,也没有任何其他操作),冷却剩余轮数减 ;
  2. 否则必须接单:把本轮订单加入已接集合;
  3. 接单后若集合大小超过 ,必须立即退货:从已接订单(含刚接入的这份)中退掉报酬最小的一份;若报酬最小的订单有多份,退其中到来编号最小的一份。每次退货都会使柜台进入冷却期,其后连续 轮不能接单。

被退掉的订单彻底消失。求流程结束后保留订单的报酬总和,以及整个过程的退货次数。(若允许每次自选退哪一份,最终报酬总和也不会超过这里的结果。)

输入格式

第一行三个整数 。

第二行 个整数 。

输出格式

两行,每行一个整数:第一行是保留订单的报酬总和,第二行是退货次数。

样例 1

样例

输入
5 2 0
3 1 4 1 5
输出
9
3

,退货不触发任何冷却:保留集合依次变为 、、退报酬 后 、退报酬 后 、退报酬 后 ,报酬总和 ,退货 次。

样例 2

第 轮接单后集合 超容量,退掉报酬最小的刚接入订单(报酬 ),柜台在第 两轮冷却,报酬 的订单因此被跳过;第 轮接单后又退掉报酬 。最终保留 ,总和 ,退货 次。

数据范围

;;。报酬总和可能超过 位整数范围。

输入
输出

            
答案