백준 17135 캐슬 디펜스

문제 링크:

17135번: 캐슬 디펜스

코드:

/* 1. back()은 !empty() 조건 하에 사용할 것! */
/* 2. 매 k가 바뀔 때마다 ans 갱신하려면 for(k) body 밖이 아니라 안 맨 끝에서 갱신해야 */
/* 3. 매 k가 바뀔 때마다 초기상태로 바꾸려면 원본과 임시 2개 자료구조 생성해야 */
/* 4. x에 대해 dst_init이 여러번 수행 되기에, memoization하기 */

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <unordered_set>

using namespace std;

int N, M, D;
bool foe;
int foen;
/* 3 */
vector<pair<int, int>> foes, foesk;	// foe# -> r, c
vector<pair<int, int>> row, rowk;	// -> r, foe#
vector<tuple<int, int, int>> dst, dsti, dstj, dstk;	//  -> dst, c, foe#
unordered_set<int> set;
int killed, ans;

bool cmp(tuple<int, int, int> &a, tuple<int, int, int> &b) {
	if (get<0>(a) == get<0>(b))
		return get<1>(a) > get<1>(b);
	return get<0>(a) > get<0>(b);
}

void dst_init(vector<tuple<int, int, int>> &dstx, int x) {
	dstx = dst;
	for (int foei = 0; foei < foen; ++foei) {
		get<0>(dstx[foei]) += abs(x - foes[foei].second);
	}
	sort(dstx.begin(), dstx.end(), cmp);
}

int kill(vector<tuple<int, int, int>> &dstx, int t) {
	while (!dstx.empty() && foesk[get<2>(dstx.back())].first == -1) {	/* 1 */
		dstx.pop_back();
	}
	/* 1 */
	if (!dstx.empty() && get<0>(dstx.back()) <= D + t) {		// not deleted && with in dist limit
		int ret = get<2>(dstx.back());
		dstx.pop_back();
		return ret;
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> D;
	for (int r = 0; r < N; ++r) {
		for (int c = 0; c < M; ++c) {
			cin >> foe;
			if (foe) {
				foes.emplace_back(r, c);
				dst.emplace_back(N - r, c, foen);
				row.emplace_back(r, foen);
				foen++;
			}
		}
	}
	sort(row.begin(), row.end());

	/* 4 */
	vector<vector<tuple<int, int, int>>> dsts(M, dst);
	for (int i = 0; i < M; ++i)
		dst_init(dsts[i], i);

	for (int i = 0; i < M; ++i) {
		for (int j = i + 1; j < M; ++j) {
			for (int k = j + 1; k < M; ++k) {
				foesk = foes;
				dsti = dsts[i]; dstj = dsts[j]; dstk = dsts[k];	/* 4 */
				rowk = row;
				killed = 0;

				for (int t = 0; !rowk.empty() ; ++t) {
					set.clear();
					set.emplace(kill(dsti, t));
					set.emplace(kill(dstj, t));
					set.emplace(kill(dstk, t));
					for (auto foei : set) {
						if (foei == -1)
							continue;
						++killed;
						foesk[foei] = make_pair(-1, -1);
					}

					while (!rowk.empty() && rowk.back().first >= N - 1 - t) {	/* 1 */
						foesk[rowk.back().second] = make_pair(-1, -1);
						rowk.pop_back();
					}
				}
				if (killed > ans)	/* 2 */
					ans = killed;
			}
		}
	}

	cout << ans;
	return 0;
}