PKU 3171 Cleaning Shifts

• 動的計画法
• 時間->コスト の表をmapでsparseに持たせている
• 牛で2重ループを回しても間に合うらしい

struct Cow {
	int T1, T2, S;
	bool operator < (const Cow& rh) const {
		return T1 != rh.T1 ? T1 < rh.T1 :
			T2 != rh.T2 ? T2 < rh.T2 :
			S < rh.S;
	}
};

int main() {
	// 単調増加な関数のイベントポイントのみを保持する
	int N, M, E;
	cin >> N >> M >> E;
	vector<Cow> cows;
	REP(n, N) {
		Cow cow;
		cin >> cow.T1 >> cow.T2 >> cow.S;
		++cow.T2;	// [T1, T2)に変更する
		cows.push_back(cow);
	}

	sort(ALL(cows));

	map<int, ll> f;
	f[M] = 0;
	for (vector<Cow>::iterator it = cows.begin(), itEnd = cows.end(); it != itEnd; ++it) {
		const Cow& cow = *it;

		// 仕事の引継元となる牛を探す
		map<int, ll>::iterator jt = f.lower_bound(cow.T1);
		if (jt == f.end()) {
			// 仕事の引継ぎ元となる牛がいなかった
			continue;
		}

		map<int, ll>::iterator kt = f.lower_bound(cow.T2);
		const ll nextCost = jt->second + cow.S;
		if (kt == f.end() || nextCost <= kt->second) {
			f[cow.T2] = nextCost;
			kt = f.lower_bound(cow.T2);

			// コストの高い経路を削除する
			map<int, ll>::iterator lt = jt;
			while (lt != kt) {
				if (lt->second >= nextCost) {
					map<int, ll>::iterator mt = lt;
					++mt;
					f.erase(lt);
					lt = mt;
				} else {
					++lt;
				}
			}
		}
	}

	if (f.count(E + 1)) {
		cout << f[E + 1] << endl;
	} else {
		cout << -1 << endl;
	}
}