SPOJ – PARTY – Party Schedule

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[101][502];
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. }
42. int main()
43. {
44. ll si;
45. while(scanf(“%lld%lld”,&si,&n) && (si!=0 || n!=0))
46. {
47. ll i,j;
49. for(i=0;i<=100;i++)
50. {
51. for(j=0;j<=500;j++)
52. dp[i][j]=-1;
53. }
54. for(i=0;i<n;i++)
55. {
56. scll(s[i]);scll(v[i]);
57. }
58. ll k=ks(0,si);
59. ll low=0,high=si,mid;
60. while(low<high)
61. {
62. mid=(low+high)/2;
63. if(ks(0,mid)<k)
64. low=mid+1;
65. else
66. high=mid;
67. }
68. printf(“%lld %lld\n“,high,k);
69. }
70. return 0;

71. }