BOJ 31913 기초마법학

문제 링크입니다.

관찰

가능한 모든 직사각형을 확인해 볼 수는 없습니다.

모든 직사각형의 왼쪽 아래 점이 (0, 0)으로 고정되어 있습니다.

직사각형을 쭉 당겨서 K종류의 색깔이 모두 들어가게 만들었다고 합시다. 그러면 그 직사각형보다 가로 세로 길이가 모두 크거나 같은 직사각형은 역시 K종류의 색깔이 모두 들어갑니다.

그래서, 직사각형의 가로 길이가 증가함에 따라 가능한 세로 길이의 최댓값은 단조 감소합니다.

가능한 많은 점이 들어가야 하니, 직사각형은 될 수 있으면 큰 편이 좋습니다.

쓸고 지나가기

방향성을 가지고 점을 확인하는 건 좋은 분석 방법입니다.

점들을 x좌표 → y좌표 기준으로 오름차순 정렬해 순서대로 마법진에 추가한다고 해봅시다. 마법진은 점을 추가하면 그에 맞게 적당히 늘어난다 칩시다. 이제 직사각형의 가로 길이는 무시해도 좋습니다.

세로 길이 관리하기

점을 추가하다가 K개의 색깔이 모두 있는 상태가 되었다면, 직사각형 안의 색깔 종류가 K-1개가 될 때까지 직사각형의 세로 길이를 줄여야 합니다. 우선순위 큐와 같이 정렬성이 유지되는 자료 구조를 활용하고, 현재 마법진 내의 각 색깔 점의 개수를 저장해 두면 쉽게 처리할 수 있습니다.

그 뒤로 점을 추가할 때는 y좌표를 확인해 제거했던 점이 다시 직사각형에 들어오지 않도록 상한을 잡아주면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int cnt[12345];
ll ans, now;
priority_queue<tuple<int,ll,int>> pq;
vector<tuple<int,int,ll,int>> v;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i++){
		int x, y, p, c; cin >> x >> y >> p >> c;
		v.push_back({x, y, p, c});
	}
	sort(v.begin(), v.end());
	int maxh = 1234567890;
	for(int i = 0; i < n; i++){
		auto [x,y,p,c] = v[i];
		pq.push({y,p,c});
		now += p;
		if(!cnt[c]) cnt[0]++;
		cnt[c]++;
		if(i == n-1 || get<0>(v[i+1]) != x){
		while(pq.size()){
			auto [yy, pp, cc] = pq.top();
			if(cnt[0] != k && yy <= maxh) break;
			pq.pop();
			now -= pp;
			cnt[cc]--;
			if(!cnt[cc]) cnt[0]--;
			maxh = min(maxh, yy-1);
		}
		ans = max(ans, now);
		}
	}
	cout << ans;
}