Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <memory.h>
- #include <ctime>
- #include <bitset>
- #include <unordered_map>
- using namespace std;
- #define ABS(a) ((a>0)?a:-(a))
- #define MIN(a,b) ((a<b)?(a):(b))
- #define MAX(a,b) ((a<b)?(b):(a))
- #define FOR(i,a,n) for (int i=(a);i<(n);++i)
- #define FI(i,n) for (int i=0; i<(n); ++i)
- #define pnt pair <int, int>
- #define mp make_pair
- #define PI 3.1415926535897
- #define MEMS(a,b) memset(a,b,sizeof(a))
- #define LL long long
- #define U unsigned
- vector<int> a,b;
- vector<int> c;
- int main()
- {
- #ifdef Fcdkbear
- freopen("in.txt", "r", stdin);
- double beg = clock();
- //freopen("out.txt", "w", stdout);
- #endif
- int n,m;
- scanf("%d%d",&n,&m);
- a.resize(n);
- b.resize(m);
- FOR(i,0,n)
- scanf("%d",&a[i]);
- FOR(i,0,m)
- scanf("%d",&b[i]);
- sort(a.rbegin(), a.rend());
- sort(b.rbegin(), b.rend());
- int res = 0;
- int l = 1, r = m;
- while (l<=r)
- {
- int mid = (l+r) / 2;
- c.clear();
- for (int i = mid - 1; i >= 0; --i)
- c.push_back(b[i]);
- LL have1 = 1;
- LL have2 = 0;
- int lev = 0;
- int p1 = 0;
- int p2 = 0;
- bool f = true;
- while (1)
- {
- while ((p1<c.size()) && (c[p1] == lev) && (have1>0))
- {
- have1--;
- p1++;
- }
- if (p1 == c.size())
- break;
- if (have1 == 0)
- {
- f = false;
- break;
- }
- while ((have1) && (p2 < a.size()))
- {
- have1--;
- have2+=a[p2];
- p2++;
- }
- if (p2 == a.size())
- {
- if (have1+have2<(int)c.size() - p1)
- f = false;
- break;
- }
- have1 = have2;
- have2 = 0;
- lev++;
- }
- if (f)
- {
- res = mid;
- l = mid + 1;
- }
- else
- r = mid - 1;
- }
- cout<<res<<endl;
- #ifdef Fcdkbear
- double end = clock();
- fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement