Advertisement
Guest User

Untitled

a guest
Oct 29th, 2014
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. //Abinash Ghosh(Om)
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <climits>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <vector>
  11. #include <list>
  12. #include <stack>
  13. #include <queue>
  14. #include <map>
  15. #include <set>
  16. #include <string>
  17. #include <utility>
  18. #include <sstream>
  19. #include <algorithm>
  20. using  namespace  std;
  21.  
  22. #define PI acos(-1.0)
  23. #define MAX 10000007
  24. #define EPS 1e-9
  25. #define mem(a,b) memset(a,b,sizeof(a))
  26. #define gcd(a,b) __gcd(a,b)
  27. #define pb push_back
  28. #define mp make_pair
  29. #define x first
  30. #define y second
  31. #define Sort(x) sort(x.begin(),x.end())
  32. #define FOR(i, b, e) for(int i = b; i <= e; i++)
  33. #define pr(x) cout<<x<<"\n"
  34. #define pr2(x,y) cout<<x<<" "<<y<<"\n"
  35. #define pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
  36. #define READ(f) freopen(f, "r", stdin)
  37. #define WRITE(f) freopen(f, "w", stdout)
  38.  
  39. typedef  long long ll;
  40. typedef  pair <int, int> pii;
  41. typedef  pair <double , double> pdd;
  42. typedef  pair <ll , ll > pll;
  43. typedef  vector <int> vi;
  44. typedef  vector <pii> vpii;
  45. typedef  vector <ll > vl;
  46.  
  47.  
  48. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  49. //int dx[]={1,1,0,-1,-1,-1,0,1};
  50. //int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  51. //int dx[]={2,1,-1,-2,-2,-1,1,2};
  52. //int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  53. ll wait[100005],qt[10004];
  54. bool cmp(ll a,ll b)
  55. {
  56.     return a>b;
  57. }
  58. struct qp
  59. {
  60.     ll nxt,tv;
  61.     bool operator<(const qp& p)const
  62.     {
  63.         return nxt >p.nxt;
  64.     }
  65. };
  66. int main()
  67. {
  68.     //READ("in.txt");
  69.     //WRITE("out.txt");
  70.     int T,n,q;
  71.     scanf("%d",&T);
  72.     FOR(t,1,T)
  73.     {
  74.         scanf("%d%d",&n,&q);
  75.         FOR(i,0,n-1)
  76.         scanf("%lld",&wait[i]);
  77.         sort(wait,wait+n,cmp);
  78.         FOR(i,0,q-1)
  79.         scanf("%lld",&qt[i]);
  80.         sort(qt,qt+q);
  81.         priority_queue<qp>Q;
  82.         FOR(i,0,q-1)
  83.         {
  84.             qp a;
  85.             a.nxt=0;
  86.             a.tv=qt[i];
  87.             Q.push(a);
  88.         }
  89.         ll cur , total,ans=-1;
  90.         FOR(i,0,n-1)
  91.         {
  92.             qp temp=Q.top();
  93.             Q.pop();
  94.             cur=temp.nxt+wait[i];
  95.             if(ans<cur)ans=cur;
  96.             temp.nxt=temp.tv+temp.nxt;
  97.             Q.push(temp);
  98.         }
  99.         //Q.clear();
  100.         printf("Case %d: %lld\n",t,ans);
  101.     }
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement