시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB83928422136.349%

문제

혁진이는 일을 많이 벌여놓는 것을 좋아한다. 어느 날, 혁진이는 무작정 일을 많이 벌여놓고는 이 수많은 일을 어떻게 처리해야 할지 몰라 곤란해하고 있다. 어떤 순서로 일을 해야 가장 효율적일지를 고민하던 혁진이는 자료구조 시간에 공부한 내용을 바탕으로 좋은 방법을 생각해냈다. 혁진이가 생각한 방법은 매우 단순하다. 일마다 처리하는데 걸리는 시간을 저장해놓고, 일이 주어진 순서대로 한 개씩 처리하는 것이다.

똑똑한 혁진이는 자신이 생각한 방법을 가장 잘 다룰 수 있는 자료구조가 바로 큐(Queue)라는 것쯤은 이미 알고 있었다. 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 데이터를 저장하는 방식이다.

자신이 생각한 방법대로 일을 잘 처리하던 혁진이는 이 자료구조에 아주 중요한 문제점을 발견했다. 주어진 순서대로 일을 처리하다 보면 중간에 급한 일을 먼저 하고 싶어도 앞에 있는 모든 일을 처리해야만 하는 것이다. 혁진이는 일할 수 있는 시간이 정해져 있어서, 주어진 순서대로 일을 처리하다 보면 중간에 있는 급한 일을 처리할 수도 있고, 못할 수도 있는 상황이 생긴다. 혁진이는 중간에 있는 일을 처리할 수 있는지 알아보려면, 먼저 자신이 일할 수 있는 시간 동안 몇 개의 일을 처리할 수 있는지 예측할 수 있어야 한다고 생각했다.

혁진이는 이러한 기능을 갖춘 새로운 자료구조인 예측 큐(Predictable Queue)를 만들려고 한다. 혁진이를 도와 혁진이가 일할 수 있는 시간 동안 몇 개의 일을 처리할 수 있는지 알아보자.

입력

첫 번째 줄에는 혁진이가 벌여놓은 일의 개수와 일할 수 있는 시간 동안 몇 개의 일을 처리할 수 있는지 알아볼 개수를 의미하는 정수 N, M (1 ≤ N, M ≤ 200,000)이 주어진다.

두 번째 줄에는 공백으로 구분된 N개의 정수 t1, t2, ..., tN (1 ≤ ti ≤ 10,000)이 주어진다. ti는 큐에 들어가는 각 일의 시간을 의미하며, 가장 왼편에 있는 일이 가장 먼저 주어진 일이다.

다음 M개의 각 줄에는 혁진이가 일할 수 있는 시간을 의미하는 정수 T (1 ≤ T ≤ 2×109)가 주어진다.

출력

M개의 각 줄에 혁진이가 일할 수 있는 시간 동안 처리할 수 있는 일의 개수를 출력한다.

예제 입력 1

7 4
1 2 3 1 2 3 1
1
8
11
14

예제 출력 1

1
4
5
7

출처

University > 충남대학교 > 제2회 생각하는 프로그래밍 대회 H번

  • 문제를 만든 사람: isku