백준 21279번 광부 호석

문제 요약

점 $(X_i, Y_i)$가 $N$개 주어진다. 이 때, $(0, 0)$을 왼쪽 아래 꼭짓점으로 하고 $(H, W)$를 오른쪽 위 꼭짓점으로 하는 직사각형을 그리고자 한다. 이 때, 직사각형에 포함되는 점의 개수는 최대 $C$개이다.

각 점에 대응하는 가치인 $V_i$도 주어지는데 조건을 만족하는 직사각형 중에서 포함되는 점들의 가치의 합이 최대가 되게 그렸을 때의 그 최댓값을 출력해야 한다.

$ 1 \le N \le 500,000$, $1 \le C \le N$, $ 0 \le X_i, Y_i \le 100,000$, $1 \le V_i \le 10^8$

풀이

우리가 그리고자 하는 직사각형의 오른쪽 위 꼭짓점을 위주로 풀이를 진행해보자. 이 꼭짓점의 $y$좌표를 $a$로 고정했다고 하자.

그러면 $y$좌표가 $a$일 때, 최대로 얻을 수 있는 가치의 합은 최대한 직사각형을 크게 그렸을 때이다. $V_i$는 1보다 크거나 같기 때문이다.

그렇게 $a$일 때, 최대한 크게 직사각형을 그렸을 때의 $x$좌표를 $b$라고 하자.

이제 $y$좌표를 $a \lt c$인 $c$로 고정해보자. 이 $c$에서 최대한 크게 그린 직사각형을 생각해보자.

그 떄의 오른쪽 위 꼭짓점의 $x$좌표를 $d$라고 하면 $d \le b$임을 알 수 있다. 이걸 말로 풀어서 표현하자면, $y$좌표를 고정했을 때, 최대한 크게 직사각형을 그렸을 때의 오른쪽 위 꼭짓점의 $x$좌표는 $y$좌표가 커질수록 적어도 커지진 않는다는 뜻이다.

그러한 점들을 만약에 평면상에 찍어서 그려본다면 왼쪽 위로 올라가는 계단 형식으로 그려질 것이다.

이를 이용해서 문제를 해결할 수 있다.

제일 처음에 $y$좌표는 0부터, 그리고 $x$좌표는 $y=0$에서 포함할 수 있는 최대한 크게 그린다.

그러면서 만약 현재 포함된 점들의 개수가 $C$보다 작거나 같다면 $y$를 1 키우고 현재 $x$좌표까지의 점들을 모두 추가한다.

이 때, 포함된 점의 개수가 $C$보다 크다면 $x$를 1씩 줄여나가면서 포함된 점들 중에서 $x$좌표가 현재의 $x$값보다 큰 애들을 빼낸다.

이 과정을 반복하면 최댓값을 구할 수 있다. 시간 복잡도는 모든 점들이 최대 한 번 포함되고, 최대 한 번 빠지기 때문에 $O(N)$이다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 1;
const int MAX = 1e5 + 5;
vector<vector<pair<int,int>>> X(MAX), Y(MAX);
ll value[MAXN];
int N, C, cost;
ll ans, sum;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> C;
    for(int i=1;i<=N;++i) {
        int x, y;
        cin >> x >> y >> value[i];
        X[x].emplace_back(y, i);
        Y[y].emplace_back(x, i);
    }
    int y = 0, x = 100000;
    while(y <= 100001 && x >= 0) {
        ans = max(ans, sum * (cost <= C) * 1LL);
        if(cost <= C) {
            for(pair<int,int> p : Y[y++]) {
                if(p.first <= x) {
                    ++cost;
                    sum += value[p.second];
                }
            }
        }
        else {
            for(pair<int,int> p : X[x--]) {
                if(p.first < y) {
                    --cost;
                    sum -= value[p.second];
                }
            }
        }
        ans = max(ans, sum * (cost <= C) * 1LL);
    }
    ans = max(ans, sum * (cost <= C) * 1LL);
    cout << ans << '\n';
    return 0;
}