Cow Exhibition

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 long long INF = 1e12;
 8 const int MAX = 200009;
 9 long long dp[MAX];
10 int N;
11 
12 int main()
13 {
14     while(cin>>N)
15     {
16         int s[105],t[105];
17         for(int i = 0;i <MAX;i++)
18             dp[i] = -INF;
19             dp[100000] = 0;
20         for(int i = 1;i <= N;i++)
21             scanf("%d %d",&s[i],&t[i]);
22 
23         for(int i =1;i <=N;i++)
24         {
25             if(s[i]< 0&&t[i] < 0)
26                 continue;
27             if(s[i]>0)
28             {
29                 for(int j = 200000;j>=s[i];j--)
30                     if(dp[j-s[i]]>-INF)
31                     {
32                         dp[j] = max(dp[j],dp[j-s[i]]+t[i]);
33                     }
34 
35             }
36             else
37             {
38                 for(int j =s[i];j <=200000+s[i];j++ )
39                     if(dp[j-s[i]]>-INF)
40                     {
41                         dp[j] = max(dp[j],dp[j-s[i]]+t[i]);
42                     }
43 
44             }
45         }
46         long long max1 = 0;
47         for(int i = 100000;i <=200000;i++)
48             if(dp[i]>0&&dp[i]+i-100000)
49             max1 = max(max1,dp[i]+i-100000) ;
50         cout<<max1<<endl;
51     }
52 
53     return 0;
54 }