백준 19644, 좀비 떼가 기관총 진지에도 오다니

https://www.acmicpc.net/problem/19644

19644번: 좀비 떼가 기관총 진지에도 오다니

 

 

요약

 

 

주어진 조건으로 처리할 수 없는 좀비가 C개 이하인지 여부를 구한다.

---

1. 좀비와의 거리와 체력, 기관총의 사거리와 공격력, 지뢰의 개수가 주어진다. 만약 좀비의 체력이 기관총을 쏜 횟수 * 기관총의 공격력보다 높다면, 지뢰를 사용하여야 한다.

 

2. 기관총을 쏜 횟수 * 기관총의 공격력을 누적합으로 psum이라는 배열로 관리한다. 지뢰와 기관총을 동시에 사용할 수 없으므로, 지뢰를 사용한 곳에서는 기관총의 공격력을 더하지 않는다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, len, damage, C;
ll arr[3000001];
ll psum[3000001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	cin >> len >> damage;
	cin >> C;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) {
		ll now = psum[i - 1] - psum[max(0, i - len)];
		if (arr[i] <= now + damage) {
			psum[i] = psum[i - 1] + damage;
			continue;
		}
		else {
			if (C) {
				C--;
				psum[i] = psum[i - 1];
			}
			else {
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES";
	return 0;
}