UVa 10131 - Is Bigger Smarter?

// UVa 10131 - Is Bigger Smarter?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct elephant {
	int w, s, i;
};

bool operator <(elephant a, elephant b) {
	return a.w < b.w || a.w == b.w && a.s < b.s;
}

int main() {
	int n = 1;
	elephant e[1002];
	while (cin >> e[n].w >> e[n].s) {
		e[n].i = n;
		n++;
	}
	n--;
	sort(e + 1, e + n + 1);
	int T[1001], R[1001];
	T[0] = 0;
	R[0] = 0;
	int s = 0;
	for (int i = 1; i <= n; i++) {
		T[i] = 0;
		R[i] = 0;
		for (int j = 1; j < i; j++) {
			if (T[j] > T[i] && e[j].s > e[i].s && e[j].w < e[i].w) {
				T[i] = T[j];
				R[i] = j;
			}

		}
		T[i]++;
		if (T[i] > T[s])
			s = i;
	}
	vector<int> sol;
	while (s) {
		sol.push_back(e[s].i);
		s = R[s];
	}
	cout << sol.size() << endl;
	for (int i = sol.size() - 1; i >= 0; i--)
		cout << sol[i] << endl;
	return 0;
}