SRM 681 Div.1

300 : 정점을 압축하고 Parametric Search 하면서 Maximum Flow 돌리면 됨. 구간을 나타내는 정점을 압축할 때 구간의 경계는 분리해서 압축해야함. 예를 들어서, [L(1), R(1)], [R(1)=L(2), R(2)], ... [R(k-1)=L(k) R(k)]는 [L(1), L(1)], (L(1), R(1)), [R(1), R(1)], (R(1)=L(2), R(2)), [R(2), R(2)] ... 이런식으로. 그리디 해법이 있다는데 생각해보아야함.

500 : 가운데부터 넓혀나가면 됨. 메모리 제한이 빡빡해서 배열 별도로 잡으면 안되고, left right 포인터 2개 잡아서 하면 됨. N^2 같아보이지만, (i, X(i)) 점들을 좌표평면에서 생각하면 언덕 모양들이 나올 때에 그 언덕의 너비를 다 더하는 것인데, 한 언덕에 대해서는 변에 해당하는 것들의 언덕 너비가 다 0임. 즉 언덕 너비들을 다 더하면 많아야 N이라서 10^9+7로 나눈 나머지를 구하라는 건 fake임.