Advertisement
Guest User

Untitled

a guest
Feb 7th, 2016
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <list>
  2. #include <map>
  3. #include <set>
  4. #include <deque>
  5. #include <stack>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <memory.h>
  15. #include <ctime>
  16. #include <bitset>
  17. #include <unordered_map>
  18.  
  19. using namespace std;
  20.  
  21. #define ABS(a) ((a>0)?a:-(a))
  22. #define MIN(a,b) ((a<b)?(a):(b))
  23. #define MAX(a,b) ((a<b)?(b):(a))
  24. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  25. #define FI(i,n) for (int i=0; i<(n); ++i)
  26. #define pnt pair <int, int>
  27. #define mp make_pair
  28. #define PI 3.1415926535897
  29. #define MEMS(a,b) memset(a,b,sizeof(a))
  30. #define LL long long
  31. #define U unsigned
  32.  
  33. vector<int> a,b;
  34. vector<int> c;
  35.  
  36. int main()
  37. {
  38. #ifdef Fcdkbear
  39.     freopen("in.txt", "r", stdin);
  40.     double beg = clock();
  41.     //freopen("out.txt", "w", stdout);
  42. #endif
  43.  
  44.     int n,m;
  45.     scanf("%d%d",&n,&m);
  46.     a.resize(n);
  47.     b.resize(m);
  48.     FOR(i,0,n)
  49.         scanf("%d",&a[i]);
  50.     FOR(i,0,m)
  51.         scanf("%d",&b[i]);
  52.     sort(a.rbegin(), a.rend());
  53.     sort(b.rbegin(), b.rend());
  54.     int res = 0;
  55.     int l = 1, r = m;
  56.     while (l<=r)
  57.     {
  58.         int mid = (l+r) / 2;
  59.         c.clear();
  60.         for (int i = mid - 1; i >= 0; --i)
  61.             c.push_back(b[i]);
  62.         LL have1 = 1;
  63.         LL have2 = 0;
  64.         int lev = 0;
  65.         int p1 = 0;
  66.         int p2 = 0;
  67.         bool f = true;
  68.         while (1)
  69.         {
  70.             while ((p1<c.size()) && (c[p1] == lev) && (have1>0))
  71.             {
  72.                 have1--;
  73.                 p1++;
  74.             }
  75.             if (p1 == c.size())
  76.                 break;
  77.             if (have1 == 0)
  78.             {
  79.                 f = false;
  80.                 break;
  81.             }
  82.             while ((have1) && (p2 < a.size()))
  83.             {
  84.                 have1--;
  85.                 have2+=a[p2];
  86.                 p2++;
  87.             }
  88.             if (p2 == a.size())
  89.             {
  90.                 if (have1+have2<(int)c.size() - p1)
  91.                     f = false;
  92.                 break;
  93.             }
  94.             have1 = have2;
  95.             have2 = 0;
  96.             lev++;
  97.         }
  98.         if (f)
  99.         {
  100.             res = mid;
  101.             l = mid + 1;
  102.         }
  103.         else
  104.             r = mid - 1;
  105.     }
  106.     cout<<res<<endl;
  107.  
  108.  
  109.  
  110. #ifdef Fcdkbear
  111.     double end = clock();
  112.     fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
  113. #endif
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement