SPOJ – WACHOVIA – Wachovia Bank

1. #include<stdio.h>

2. #include<iostream>
3. #include<string>
4. #define sci(x) scanf(“%d”,&x)
5. #define scll(x) scanf(“%lld”,&x)
6. #define pfi(x) printf(“%d”,x)
7. #define pfll(x) printf(“%lld”,x)
8. #define ch(x) scanf(“%c”,&x)
9. using namespace std;
10. typedef long long ll;
11. /*float stof(const string& str, size_t *idx = 0);
12. double stod(const string& str, size_t *idx = 0);
13. long double stold(const string& str, size_t *idx = 0);
14. int stoi(const string& str, size_t *idx = 0, int base = 10);
15. long stol(const string& str, size_t *idx = 0, int base = 10);
16. unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
17. long long stoll(const string& str, size_t *idx = 0, int base = 10);
18. unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
19. ll max(ll a,ll b)
20. {
21. if(a>b)
22. return a;
23. else
24. return b;
25. }
26. ll n;
27. ll dp[52][1002];
28. ll s[2003];
29. ll v[2003];
30. ll ks(ll idx,ll rs)
31. {
32. if(idx==n || rs==0)
33. return 0;
34. if(dp[idx][rs]!=-1)
35. return dp[idx][rs];
36. if(s[idx]<=rs)
37. return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
38. if(s[idx]>rs)
39. return dp[idx][rs]=ks(idx+1,rs);
40. }
41. int main()
42. {
43. ll si;ll t;
44. scll(t);
45. while(t–)
46. {
47. scll(si);
48. scll(n);
49. ll i,j;
51. for(i=0;i<=50;i++)
52. {
53. for(j=0;j<=1000;j++)
54. dp[i][j]=-1;
55. }
56. for(i=0;i<n;i++)
57. {
58. scll(s[i]);scll(v[i]);
59. }
60. ll k=ks(0,si);
61. printf(“Hey stupid robber, you can get %lld.\n“,k);
62. }
63. return 0;

64. }