AtCoder Regular Contest 070E: NarrowRectangles

http://arc070.contest.atcoder.jp/tasks/arc070_c

関数dpとかいうやつ。僕のいうところの「愚直に値を持つ」dpと同じです。
愚直にx座標すべて持ってみることを考えて、実は本当に持つ必要があるものは少なくて、更新も簡単にできる、みたいな感じです。
|x-c|を足すと、x=cで傾きが2変わることを失念してWA生やしました。
あとsetで最後の要素を消すのはS.erase(--S.end())です。

dpというとこのパターンと、考察して状態量を減らすパターンがあるのかな?前者はなんとかなりそうだけど、後者は一般的な解き方がなくて難しそう。

int N;
multiset<ll> L, R;
int A[MAX_N], B[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i] >> B[i];
	ll a = A[0], b = A[0];
	L.insert(A[0]); R.insert(A[0]);
	ll ans = 0;
	rep(i, 1, N) {
		a -= B[i] - A[i];
		b += B[i - 1] - A[i - 1];
		ll l = *L.rbegin(), r = *R.begin();
		if(a <= A[i] && A[i] <= b) {
			L.insert(A[i] - (a - l));
			R.insert(A[i] - (b - r));
			a = A[i]; b = A[i];
		}
		else if(A[i] < a) {
			ans += abs(A[i] - a);
			L.insert(A[i] - (a - l));
			L.insert(A[i] - (a - l));
			ll le = *L.rbegin() + (a - l);
			L.erase(--L.end());
			R.insert(le - (b - r));
			a = *L.rbegin() + (a - l);
			b = le;
		}
		else {
			ans += abs(A[i] - b);
			R.insert(A[i] - (b - r));
			R.insert(A[i] - (b - r));
			ll rb = *R.begin() + (b - r);
			R.erase(R.begin());
			L.insert(rb - (a - l));
			a = rb;
			b = *R.begin() + (b - r);
		}
	}
	cout << ans << "\n";
}