Submission #2544922

---

Source Code Expand

#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int n;
const int INF = 1e9;

struct Box {
	int w;
	int h;

	bool operator< (const Box &o) const {
		return h == o.h ? w > o.w : h < o.h;
	}
};

int main() {
	cin >> n;
	vector <Box> box(n);
	rep (i, n) {
		cin >> box[i].w >> box[i].h;
	}

	sort(box.begin(), box.end());

	vector <int> dp(n, INF);
	rep (i, n) {
		*lower_bound(dp.begin(), dp.end(), box[i].w) = box[i].w;
	}

	cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << endl;

	return 0;
}

Submission Info

Judge Result