SHARE
TWEET

Untitled

a guest Jun 19th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Nishat Tasnim Ahmed Meem
  3.     Shahjalal University Of Science & Technology, '13batch
  4. */
  5.  
  6. #include<iostream>
  7. #include<sstream>
  8. #include<cstdio>
  9. #include<cstring>
  10. #include<cstdlib>
  11. #include<cmath>
  12. #include<algorithm>
  13. #include<vector>
  14. #include<string>
  15. #include<stack>
  16. #include<queue>
  17. #include<deque>
  18. #include<map>
  19. #include<sstream>
  20. #include<set>
  21. #include<utility>
  22.  
  23. using namespace std;
  24.  
  25. #define inf 1<<28
  26. #define ll long long
  27. #define sf1(a) scanf("%d",&a)
  28. #define sf2(a,b) scanf("%d %d",&a,&b)
  29. #define sf3(a,b,c) scanf("%d %d %d", &a,&b, &c)
  30. #define sf4(a,b,c, d) scanf("%d %d %d %d", &a,&b, &c, &d)
  31. #define sf1ll(a) scanf("%lld",&a)
  32. #define sf2ll(a,b) scanf("%lld %lld",&a,&b)
  33. #define sf3ll(a,b,c) scanf("%lld %lld %lld", &a,&b, &c)
  34. #define sf4ll(a,b,c, d) scanf("%lld %lld %lld %lld", &a,&b, &c, &d)
  35. #define pi acos(-1)
  36. #define sz 10000+10
  37. #define pii pair<int, int>
  38. #define clr(a) memset(a, 0, sizeof a)
  39. #define clr1(a) memset(a, -1, sizeof a)
  40.  
  41. template<class T> T power(T N,T P)
  42. {
  43.     return (P==0)?  1: N*power(N,P-1);   //N^P
  44. }
  45. template<class T> T gcd(T a,T b)
  46. {
  47.     if(b == 0)return a;    //gcd(a,b)
  48.     return gcd(b,a%b);
  49. }
  50.  
  51. template<class T1> void deb(T1 e1)
  52. {
  53.     cout<<e1<<endl;
  54. }
  55. template<class T1,class T2> void deb(T1 e1,T2 e2)
  56. {
  57.     cout<<e1<<" "<<e2<<endl;
  58. }
  59. template<class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3)
  60. {
  61.     cout<<e1<<" "<<e2<<" "<<e3<<endl;
  62. }
  63. template<class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4)
  64. {
  65.     cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
  66. }
  67. template<class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
  68. {
  69.     cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
  70. }
  71. template<class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6)
  72. {
  73.     cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;
  74. }
  75.  
  76. //ll BigMod(ll B,ll P,ll M){ ll R=1; while(P>0)  {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M
  77.  
  78. //ll gcd(ll a,ll b){if(b == 0)return a;return gcd(b,a%b);}
  79. //ll lcm(ll a,ll b){return (a/gcd(a,b))*b;}
  80.  
  81.  
  82. //int Set(int N,int pos){return N=N | (1<<pos);}
  83. //int Reset(int N,int pos){return N= N & ~(1<<pos);}
  84. //bool Check(int N,int pos){return (bool)(N & (1<<pos));}
  85. //N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) )://XOR of 1-n numbers
  86.  
  87. int dx[] = { 0, 1,  0, -1, -1, 1,  1, -1 };
  88. int dy[] = { 1, 0, -1,  0,  1, 1, -1, -1 };
  89. int xx[] = { -1, 1, 2, 2,  1, -1, -2, -2 };
  90. int yy[] = {  2, 2, 1,-1, -2, -2, -1,  1 };
  91.  
  92. int dp[110][110], arr[110], n, w, k;
  93.  
  94. int Call(int pos, int m)
  95. {
  96.     if(pos == n || m == k) return 0;
  97.     if(dp[pos][m] != -1) return dp[pos][m];
  98.  
  99.     int ret1, ret2, cnt=1, i=pos+1, t=w+arr[pos];
  100.     ret1 = Call(pos+1, m);
  101.     while(i<n && arr[i]<=t)
  102.     {
  103.         i++;
  104.         cnt++;
  105.     }
  106.     ret2 = cnt + Call(i, m+1);
  107.     return dp[pos][m] = max(ret1, ret2);
  108. }
  109.  
  110. int main()
  111. {
  112.     #ifndef ONLINE_JUDGE
  113.         //freopen("input.txt", "r", stdin);
  114.     #endif // ONLINE_JUDGE
  115.  
  116.     int i, tcase, cs=1, x, y;
  117.     sf1(tcase);
  118.  
  119.     while(tcase--)
  120.     {
  121.         sf3(n, w, k);
  122.         for(i=0; i<n; i++)
  123.         {
  124.             sf2(x, y);
  125.             arr[i] = y;
  126.         }
  127.         sort(arr, arr+n);
  128.         memset(dp, -1, sizeof dp);
  129.         printf("Case %d: %d\n", cs++, Call(0, 0));
  130.     }
  131.  
  132.     return 0;
  133. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top