JOISC19 Dishes

문제

oj.uz/problem/view/JOI19_dishes

문제 보기 - Two Dishes (JOI19_dishes) :: oj.uz

두가지 요리가 있고, 각 요리를 완성하기 위해서는 각각 $N$, $M$개의 단계를 거쳐야 한다. 각 단계마다 수행하는 시간이 주어지고, 각 단계를 $A_i$ 시간 이하로 끝낸다면 $B_i$의 보상을 받을 수 있다. 각 요리의 단계들은 순서대로 시행해야 하며, 두 요리의 단계들을 번갈아 가며 하는 것은 허용된다. 이 때 얻을 수 있는 보상을 최대화해야 한다.

$N<=1000000$

$M<=1000000$

 

풀이

Observation 1 : A 요리의 각 단계별로 보상을 얻기 위해 그 단계를 완료해야 하는 최대 시간 대신, 보상을 얻기 위해 A 요리의 그 단계를 끝마치기 전 수행할 수 있는 B 요리의 최대 단계를 구하자.

전체 보상의 양에는 시간이 중요한 것이 아니라 방금 구한 최대 단계만 중요하기 때문에 이를 이용하여 값을 단순화시킬 수 있다.

 

A 요리의 $i$ 단계를 끝마치기 전 수행할 수 있는 B 요리의 최대 단계를 $X_i$, B 요리의 $j$ 단계를 끝마치기 전 수행할 수 있는 A 요리의 최대 단계를 $Y_j$라고 하자. 이를 좌표평면 상에 플로팅 해보면, 다음 문제로 변형할 수 있다.

 

Observation 2 : (0, 0)에서 (N, M)으로 오른쪽, 위로 한칸씩 이동하는 경로들 중, $(i, 0)$, $(i, X_i)$를 잇는 A 선분과 경로가 교차하면 $P_i$의 보상을 받고, $(0, j)$, $(Y_j, j)$를 잇는 B 선분과 경로가 교차하면 $Q_j$의 보상을 받을 때 보상을 최대화하는 문제로 변형할 수 있다.

 

x축에는 A요리, y축에는 B요리를 놓고, A 요리의 각 단계를 완성시킬 때마다 x 값을 1 증가시키고, B 요리의 각 단계를 완성시킬 때마다 y 값을 1 증가시키는 것으로 해석하면, (0, 0)에서 시작하여 (N, M)에 도달하기까지 왼쪽 혹은 오른쪽으로만 이동하는 하나의 경로이다. 보상을 얻는 조건은 x 좌표가 $i$를 도달하는 순간 y 좌표가 $[0, X_i]$ 범위안에 있어야 한다. 이는 다시 말해 $(i, 0)$, $(i, X_i)$를 잇는 선분과 경로가 교차하면 $P_i$의 보상을 받고, $(0, j)$, $(Y_j, j)$를 잇는 선분과 경로가 교차하면 $Q_j$의 보상을 받는다.

 

Observation 3 : $(i, X_i)$는 경로 위쪽에, $(Y_j, j)$는 경로 아래쪽에 위치할 때만 보상을 받는 문제로 변형할 수 있다.

(0, 0)에서 (N, M)으로 가는 경로는 (0, 0), (N, M)의 직사각형을 정확히 두 영역으로 쪼갠다. $(i, 0)$, $(i, X_i)$를 잇는 선분과 경로가 교차하는 것과 동치인 조건은 $(i, X_i)$이 경로의 위쪽에 위치한다는 것이고, $(0, j)$, $(Y_j, j)$를 잇는 선분과 경로가 교차하는 것과 동치인 조건은 $(Y_j, j)$는 경로의 아래쪽에 위치한다는 것이다.

 

이정도의 변형으로도 문제를 해결할 수 있지만 약간의 변형을 더 할 수 있다.

 

Observation 4 : $(0, j)$, $(Y_j, j)$를 잇는 B 선분과 경로가 교차하는 조건은 $(j+1, 0)$, $(j+1, Y_j-1)$를 잇는 B' 선분과 경로가 교차하지 않는 것과 동치이다.

모든 경로가 $(0, j)$, $(Y_j, j)$를 잇는 B 선분, $(j+1, 0)$, $(j+1, Y_j-1)$를 잇는 B' 선분들 중 정확히 하나와만 겹친다는 것을 증명하면 된다. 경로가 B, B' 선분들 중 어떠한 것과도 겹치지 않고 빠져나갈 수 없다는 것은 자명하고, 둘 모두와 겹칠 수도 없으니, 둘 중 정확히 하나와만 겹친다. 따라서 기본적으로 답에 $Q_j$를 더해 놓고 B'선분을 지나면 $-Q_j$의 보상을 얻는 것으로 해석할 수 있다. 이 변형을 통해 모든 B 선분을 A선분으로 치환할 수 있다.

 

이제 지금까지 변형시킨 것을 모두 종합하면 전체 문제는 다음과 같다.

(0, 0)에서 (N, M)으로 오른쪽, 위쪽으로 한 칸씩 이동하는 경로들 중, 주어진 점이 경로에 아래쪽에 위치하면 보상을 얻을 때, 보상의 합을 최대화한다.

 

이 문제는 간단한 $O(N^2)$ DP로 해결할 수 있다.

우선, 점들을 적당히 정렬하고 펼쳐, 각 점들의 x값이 모두 다르도록 만든다.

$dp(i, j)=$ $(i, j)$에 도달하는 경로들 중 최대 보상

$dp(i, j)=max(dp(i-1, 0), ... , dp(i-1, j))$ $(j<Y_i)$

$dp(i, j)=max(dp(i-1, 0), ... , dp(i-1, j))+P_i$ $(j>=Y_i)$

 

매우 간단한 꼴의 DP 전이식이기 때문에 자료구조를 이용하여 최적화할 수 있다.

1. $dp(i, j)=max(dp(i, 0), ... , dp(i, j))$ max의 계단 꼴로 유지

2. $dp(i, j)+=P_i$ $(j>=Y_i)$ 구간에 더해줌

원래 계단 꼴이었고, 뒤쪽 구간에 $P_i$를 더하는 과정에서 깨진 계단을 다시 맞춰주는 형식이니, 요약하자면 구간에 값을 더하고, 구간에 max를 씌워주는 연산만 해결하면 된다.

두 연산 모두 교환법칙이 성립하니, lazy 세그먼트 트리를 이용하여 DP값들을 관리해주면 된다.

 

시간 복잡도 : $O(NlogN)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e6;
 
struct Point
{
	int x, y; ll w;
};
vector<Point> V;
 
int N, M;
ll ans;
 
ll A[MAXN+10], S[MAXN+10], P[MAXN+10], B[MAXN+10], T[MAXN+10], Q[MAXN+10];
 
ll dp[MAXN+10];
 
pll lazy[MAXN*4+10];
 
void busy(int node, int tl, int tr)
{
	if(tl!=tr)
	{
		lazy[node*2]={lazy[node].first+lazy[node*2].first, max(lazy[node*2].second+lazy[node].first, lazy[node].second)};
		lazy[node*2+1]={lazy[node].first+lazy[node*2+1].first, max(lazy[node*2+1].second+lazy[node].first, lazy[node].second)};
	}
	else
	{
		dp[tl]=max(dp[tl]+lazy[node].first, lazy[node].second);
	}
	lazy[node]={0, 0};
}
 
void update(int node, int tl, int tr, int l, int r, pll k)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]=k;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
}
 
ll query(int node, int tl, int tr, int p)
{
	busy(node, tl, tr);
	if(tl==tr) return dp[tl];
	int mid=tl+tr>>1;
	if(p<=mid) return query(node*2, tl, mid, p);
	else return query(node*2+1, mid+1, tr, p);
}
 
int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
	for(int i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];
 
	for(int i=1; i<=N; i++)
	{
		int t=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
		if(t<0) continue;
		if(t==M) { ans+=P[i]; continue; }
		int x=i, y=t;
		x--; y++;
		V.push_back({x, y, -P[i]}); ans+=P[i];
	}
 
	for(int i=1; i<=M; i++)
	{
		int t=upper_bound(A, A+N+1, T[i]-B[i])-A-1;
		if(t<0) continue;
		if(t==N) { ans+=Q[i]; continue; }
		int y=i, x=t;
		V.push_back({x, y, Q[i]});
	}
 
	sort(V.begin(), V.end(), [&](const Point &p, const Point &q)
	{
		if(p.x!=q.x) return p.x<q.x;
		if(p.y!=q.y) return p.y>q.y;
		return p.w>q.w;
	});
 
	for(int i=0; i<V.size(); i++)
	{
		ll t=0;
		if(V[i].y!=0) t=query(1, 0, M, V[i].y-1);
		update(1, 0, M, V[i].y, M, pll(V[i].w, t));
	}
	printf("%lld\n", query(1, 0, M, M)+ans);
}