BOJ 15554 전시회

문제 링크입니다.

문제 요약

$N$개의 순서쌍 $(A_i, B_i)$ 중 일부를 적절히 선택했을 때, $\Sigma B-\max(A)-\min(A)$의 최댓값을 주하세요.

풀이

$N$개의 순서쌍을 $A$ 기준으로 오름차순 정렬합니다. 그러면 어떤 두 순서쌍을 선택했을 때 그 사이의 순서쌍은 선택해도 손해가 없으니, 최적해는 항상 연속한 구간으로 나타남을 알 수 있습니다.

구간 $[L, R]$의 $\Sigma B$는 누적 합을 이용해 빠르게 계산할 수 있습니다. 또한 우리는 $A$의 최솟값이 $A_L$임을 알고 있으므로, 누적 합을 구할 때 $L-1$번째 항에 미리 $A_L$을 빼두는 식으로 처리하면 우리가 구해야 하는 값을 바로 얻을 수 있습니다. 우리에게 필요한 $L$은 $[1, R]$에서의 최솟값이므로, $R$을 오른쪽으로 밀면서 $L$을 현재 인덱스에서의 값과만 비교해 업데이트해줄 수 있습니다.

따라서 총 시간 복잡도 ${\cal O}(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<pll> v;
ll sumw[505050];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; v.resize(n); for(auto& i : v) cin >> i.first >> i.second;
	sort(v.begin(), v.end());
	ll ans = 0, L = 123456123456123456LL;
	for(int i = 0; i < n; i++){
		sumw[i+1] = sumw[i]+v[i].second;
		L = min(L, sumw[i]-v[i].first);
		ans = max(ans, sumw[i+1]-v[i].first-L);
	}
	cout << ans;
}