UVa 10154 - Weights and Measures

// UVa 10154 - Weights and Measures
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <limits.h>
using namespace std;

struct Turtle {
	int w;
	int s;
};

struct comp {
	bool operator()(Turtle x, Turtle y) {
		return (x.s - x.w) > (y.s - y.w);
	}
};

int main() {

	vector<Turtle> turtle;
	int w, s;
	int n = 0;
	while (cin >> w >> s) {
		Turtle tur = { w, s };
		turtle.push_back(tur);
		n++;
	}

	sort(turtle.begin(), turtle.end(), comp());

	int T[5608];
	T[0] = INT_MAX;
	for (int i = 1; i <= n; i++)
		T[i] = -1;

	for (int j = 0; j < n; j++) {
		for (int i = j + 1; i > 0; i--) {
			T[i] = max(T[i], min(T[i - 1] - turtle[j].w, turtle[j].s - turtle[j].w));
		}
	}

	int sol;
	for (sol = n; sol >= 0 && T[sol] < 0; sol--)
		;
	cout << sol << endl;

	return 0;
}