poj 2184 Cow Exhibition

poj 2184 Cow Exhibition

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;#define maxn 105#define maxs 2000 * 100#define shift 1000 * 100#define inf 0x3f3f3f3fint n, s[maxn], f[maxn];int dp[maxs];void input(){    scanf("%d", &n);    for (int i = 0; i < n; i++)        scanf("%d%d", &s[i], &f[i]);}void work(){    for (int i = 0; i < maxs; i++)        dp[i] = -inf;    dp[0 + shift] = 0;    int l = 0, r = 0;    for (int i = 0; i < n; i++)    {        l = min(l, l + s[i]);        r = max(r, r + s[i]);        int step = 1;        int begin = l, end = r;        if (s[i] > 0)        { step = -1; swap(begin, end);        }        for (int j = begin; j != end + step; j += step)        { dp[j + shift] = max(dp[j - s[i] + shift] + f[i], dp[j + shift]);        }    }    int ans = 0;    for (int i = 0; i <= r; i++)        if (dp[i + shift] >= 0) ans = max(ans, i + dp[i + shift]);    printf("%dn", ans);}int main(){    input();    work();    return 0;}