[C++] 10025 게으른 백곰

슬라이딩 윈도우와 큐를 사용한다.

 

// 10025 게으른 백곰
#include <iostream>
#include <deque>
#include <queue>
using namespace std;
#define xMAX 1000000

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, k;
	int maxSum=0, tempSum=0, length=0;
	cin >> n >> k;
	int g, x;
	int arr[xMAX + 2] = { 0, }; // 얼음의 양 저장함
	for (int i = 0; i < n; i++) {
		cin >> g >> x; // g는 얼음의 양, x는 양동이의 좌표
		if (x > length) length = x; // 최대길이
		arr[x] = g; // x좌표에는 얼음이 g 있음
	}

	queue<int> q; // 큐는 2k+1만큼의 길이여야 함
	for (int i = 0; i <= length; i++) {
		// 큐가 꽉 차있지 않으면
		if (q.size() < 2 * k + 1) {
			q.push(arr[i]);
			tempSum += arr[i];
		}
		else {
			// 큐가 꽉 차있으면
			// 일단 팝을 해주고 그 값을 뺌
			tempSum -= q.front();
			q.pop();
			// 새로운걸 넣고 그 값을 더함
			q.push(arr[i]);
			tempSum += arr[i];
		}


		if (maxSum < tempSum) maxSum = tempSum;
	}
	
	
	cout << maxSum << "\n";

	return 0;
}