[Hello 2023] C. Least Prefix Sum

 

 

---

※. pm까지의 누적합이 가장 작아야 한다.

(pm+1 ~ pn까지의 합이 0이하가 되면 안된다. -> pm 이후의 누적합을 sum이라 할 때 sum이 음수가 된다면 (pm + 음수)로

pm보다 작은값이 생기기 때문)

 ● pm+1부터 pn까지 누적합을 구하다 누적합이 0미만이 되는 순간이 있으면 누적합이 양수가 될 때 까지 우선순위큐에서     값을 빼 더해준다.

   (원소값이 양수라면 0미만이 될 수 없으므로 제외, 원소값이 음수라면 0미만이 될 수 있기 때문에 누적합에 더해주고 이     후에 누적합이 0미만이 되면 누적합 - 더해준 원소값 +(-더해준 원소값)을 해줘야 함으로 (-2*arr[i])로 우선순위큐에 넣는     다.)

 

※.pm을 포함한 이전의 누적합은 원소값보다 커야한다.

(pm이전의 누적합들은 pm까지의 누적합보다 커야한다. -> pm을 포함한 누적합이 가장 작아야 함으로 음수가 나올수록 누적합이 계속 작아진다. 그러나 양수가 나올 경우 pm을 포함한 누적합이 커지면서 어느순간 원소값이 누적합보다 작아지는 경우가 생긴다. 이 때 가장 큰 양수를 -로 변환함으로써 누적합을 작게 만든다.)

 ●pm부터 p1까지의 누적합을 구하다 누적합이 원소값보다 큰 경우가 생기면 누적합이 원소값보다 작아질때 까지 우선순위큐에서 값을 빼 더해준다.

 (원소값이 음수라면 pm을 포함한 누적합이 계속 작아지므로 제외, 원소값이 양수라면 pm을 포함한 누적합이 커지고 가장 작은 수가 아닐수도 있기 때문에 누적합이 원소값보다 크다면 누적합 - (양수원소값) + (음수로 변환된 양수원소값) 을 해줘서 누적합을 작게 만들어 준다. 때문에 양수 원소값은 (-2*arr[i])로 우선순위큐에 넣는다.)

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int n =  Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int[] arr = new int[n];
			st = new StringTokenizer(br.readLine()," ");
			for(int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			PriorityQueue<Long> prque = new PriorityQueue<>(Collections.reverseOrder());
			long ans = 0;
			long sum = 0;
			for(int i = m; i < n; i++) {
				sum += arr[i];
				if(arr[i] < 0) {
					prque.add(-2*(long)arr[i]);
				}
				while(prque.size() > 0 && sum < 0) {
					sum += prque.poll();
					ans++;
				}
			}
			
			sum = 0;
			prque = new PriorityQueue<>();
			for(int i = m-1; i >= 0; i--) {
				sum += arr[i];
				while(prque.size() > 0 && arr[i] < sum) {
					sum += prque.poll();
					ans++;
				}
				if(arr[i] > 0) {
					prque.add(-2*(long)arr[i]);
				}
			}
			if(n == 1)
				ans = 0;
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}
}