Polycarp's problems

题意翻译

Polycarp是一名资深Codehorces程序比赛参赛者。现在他想成为一位出题人。 他给协调者发去n个题目。每个题目都有它的品质，第i个问题的品质是ai(ai可以是正数，负数或0)。题目被设计成各种难度，但难度与其品质没有任何关系。 现在协调者的心情是q。在读完一个题目后，他的心情会随题目的品质而改变。也就是说当协调者读完一道品质为i的题目时，他的心情值要加上i。协调者总是从最简单的题目开始阅读，一直读到最难的题目，而想要改变这些题目的阅读顺序是不可能的。 如果协调者的心情达到了负数那么他会立刻停止阅读并且丢掉这些题。 现在Polycarp要从他的题目中移除题目以保证协调者的心情始终不会掉到负数同时移除的题目数最少。Polycarp不知道协调者现在的心情是多少，但他会猜测m次“协调者的初始心情为bi”。 对于每一个猜测，求出最少的移除题目数。 输入格式： 输入数据的第一行包括两个整数n和m(1<=n<=750,1<=m<=200000)分别表示题目总数以及猜测次数。 第二行包括n个整数 a1，a2，...，an(-10^9<=ai<=10^9)表示由易到难排列的题目的quality。 第三行包括m个整数 b1，b2，...，bn(0<=bi<=10^15)表示对于协调者初始心情的猜测。 输出格式： 输出m行，每一行包括一个整数，其中第i行表示第i次猜测对应的结果。 感谢@radish布団 提供的翻译

题目描述

Polycarp is an experienced participant in Codehorses programming contests. Now he wants to become a problemsetter. He sent to the coordinator a set of $ n $ problems. Each problem has it's quality, the quality of the $ i $ -th problem is $ a_{i} $ ( $ a_{i} $ can be positive, negative or equal to zero). The problems are ordered by expected difficulty, but the difficulty is not related to the quality in any way. The easiest problem has index $ 1 $ , the hardest problem has index $ n $ . The coordinator's mood is equal to $ q $ now. After reading a problem, the mood changes by it's quality. It means that after the coordinator reads a problem with quality $ b $ , the value $ b $ is added to his mood. The coordinator always reads problems one by one from the easiest to the hardest, it's impossible to change the order of the problems. If after reading some problem the coordinator's mood becomes negative, he immediately stops reading and rejects the problemset. Polycarp wants to remove the minimum number of problems from his problemset to make the coordinator's mood non-negative at any moment of time. Polycarp is not sure about the current coordinator's mood, but he has $ m $ guesses "the current coordinator's mood $ q=b_{i} $ ". For each of $ m $ guesses, find the minimum number of problems Polycarp needs to remove so that the coordinator's mood will always be greater or equal to $ 0 $ while he reads problems from the easiest of the remaining problems to the hardest.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ m $ ( $ 1<=n<=750 $ , $ 1<=m<=200000 $ ) — the number of problems in the problemset and the number of guesses about the current coordinator's mood. The second line of input contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ) — the qualities of the problems in order of increasing difficulty. The third line of input contains $ m $ integers $ b_{1},b_{2},...,b_{m} $ ( $ 0<=b_{i}<=10^{15} $ ) — the guesses of the current coordinator's mood $ q $ .

输出格式

Print $ m $ lines, in $ i $ -th line print single integer — the answer to the problem with $ q=b_{i} $ .

输入输出样例

输入样例 #1

6 3
8 -5 -4 1 -7 4
0 7 3

输出样例 #1

2
0
1

题意翻译

Polycarp是一名资深Codehorces程序比赛参赛者。现在他想成为一位出题人。 他给协调者发去n个题目。每个题目都有它的品质，第i个问题的品质是ai(ai可以是正数，负数或0)。题目被设计成各种难度，但难度与其品质没有任何关系。 现在协调者的心情是q。在读完一个题目后，他的心情会随题目的品质而改变。也就是说当协调者读完一道品质为i的题目时，他的心情值要加上i。协调者总是从最简单的题目开始阅读，一直读到最难的题目，而想要改变这些题目的阅读顺序是不可能的。 如果协调者的心情达到了负数那么他会立刻停止阅读并且丢掉这些题。 现在Polycarp要从他的题目中移除题目以保证协调者的心情始终不会掉到负数同时移除的题目数最少。Polycarp不知道协调者现在的心情是多少，但他会猜测m次“协调者的初始心情为bi”。 对于每一个猜测，求出最少的移除题目数。 输入格式： 输入数据的第一行包括两个整数n和m(1<=n<=750,1<=m<=200000)分别表示题目总数以及猜测次数。 第二行包括n个整数 a1，a2，...，an(-10^9<=ai<=10^9)表示由易到难排列的题目的quality。 第三行包括m个整数 b1，b2，...，bn(0<=bi<=10^15)表示对于协调者初始心情的猜测。 输出格式： 输出m行，每一行包括一个整数，其中第i行表示第i次猜测对应的结果。 感谢@radish布団 提供的翻译