백준15554 전시회

작성일 | In

문제 링크

  • http://icpc.me/15554

문제 출처

  • 2018 JOI 2번

풀이

(가치의 합) - (크기의 최댓값) + (크기의 최솟값)의 최대를 구하는 문제입니다.

일단 크기 순서대로 정렬을 해줍시다.
최댓값과 최솟값을 고정시킨 상태에서는, 그 사이에 있는 모든 그림을 포함하는 것이 당연히 이득입니다.
연속된 구간에 있는 그림의 가치의 합은 prefix sum을 이용해 빠르고 간단하게 구할 수 있습니다.

크기가 작은 그림부터 보면서 그리디하게 처리해주면 됩니다.
자세한 구현은 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n;
vector<p> v;
vector<ll> sum;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n+1); sum.resize(n+1);
	for(int i=1; i<=n; i++) cin >> v[i].x >> v[i].y;
	sort(v.begin()+1, v.end());

	for(int i=1; i<=n; i++){
		sum[i] = sum[i-1] + v[i].y;
	}

	ll ans = 0;
	int l = 1, r = 1;
	ll maxi, mini = v[1].x;
	for(int i=1; i<=n; i++){
		maxi = v[i].x;
		ll now = sum[i] - maxi + mini;
		ans = max(ans, now);
		if(i == n) break;
		mini = max(mini, v[i+1].x - sum[i]);
	}
	cout << ans;
}