#include <iostream>
using namespace std;

const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

const int maxm = 400010;
const int zero = 200000;

int n;
int f[maxm];

int main()
{
	while (scanf("%d", &n) != EOF)
	{
		memset(f, -1, sizeof(f));
		f[zero] = 0;
		for (int i = 0; i < n; i++)
		{
			int t1, t2;
			scanf("%d%d", &t1, &t2);
			if (t1 >= 0)
			{
				for (int j = maxm - 1 - t1; j >= 0; j--)
					if (f[j] != -1)
						f[j + t1] >?= f[j] + t1 + t2;
			}
			else
			{
				for (int j = -t1; j < maxm; j++)
					if (f[j] != -1)
						f[j + t1] >?= f[j] + t1 + t2;
			}
		}
		int ans = 0;
		for (int i = zero; i < maxm; i++)
			if (f[i] - i + zero >= 0)
				ans >?= f[i];
		printf("%d\n", ans);
	}
    return 0;
}

• 恭喜踩到后来加的地雷... (904) frkstyc 2008-01-30 23:25:32
  • st, check poj mail (0) Dzx 2008-01-31 00:04:10
• 同杯具…… (904) 123234345 2011-07-30 09:56:01
  • 表示无解的情况要用-INF 这样就好了 (0) 123234345 2011-07-30 10:10:49
    • +1 (0) lmm333 2011-08-23 20:39:55