← 返回题目

题库练习「SHOI2015」自动刷题机

← 上一题下一题 →

A6866 | $「SHOI2015」自动刷题机$

来源省选

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。 自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果： 1. 写了 $x$ 行代码； 2. 心情不好，删掉了之前写的 $y$ 行代码。如果 $y$ 大于当前代码长度，则相当于全部删除。 对于一个 OJ，存在某个固定的长度 $n>0$，一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后**新建一个文件**（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。

输入格式

第一行两个整数 $l, k$，表示刷题机的日志一共有 $l$ 行，一共了切了 $k$ 题。 第二行 $l$ 个整数 $x_1, \dots, x_l$。$x_i \geq 0$ 表示写了 $x_i$ 行代码，$x_i < 0$ 表示删除了这道题的 $-x_i$ 行代码。

输出格式

输出两个数 $a, b$，分别代表 $n$ 可能的最小值和最大值。如果不存在这样的 $n$ 则输出 $-1$。

输入输出样例

输入 #1

输出 #1

3 7

C++ 编辑器

输入

输出