SHARE
TWEET

Untitled

a guest Aug 22nd, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //code 1
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const int N = 10006;
  7. const int X = 100000000 + 6;
  8.  
  9. ll a[N], b[N];
  10. ll c[N];
  11.  
  12. int n, k;
  13.  
  14. ll d[N]; //new horse
  15.  
  16. bool check(ll mid) {
  17.     for (int i = 1; i <= n; ++i) {
  18.         d[i] = a[i] + b[i] * mid;
  19.     }
  20.     sort(d + 1, d + n + 1); reverse(d + 1, d + n + 1);
  21.     sort(c + 1, c + n + 1); reverse(c + 1, c + n + 1);
  22.     int cnt = 0;
  23.     int j = 1;
  24.     for (int i = 1; i <= n; ++i) {
  25.         if (d[i] > c[j]) {
  26.             ++cnt;
  27.             ++j;
  28.         }
  29.         else {
  30.             while (d[i] <= c[j] && j <= n) {
  31.                 ++j;
  32.             }
  33.             if (j > n) break;
  34.             ++cnt;
  35.             ++j;
  36.         }
  37.         if (j > n) break;
  38.     }
  39.     if (cnt >= k) return true;
  40.     else return false;
  41. }
  42.  
  43. int main () {
  44.     int T; scanf("%d", &T);
  45.     while (T--) {
  46.         scanf("%d%d", &n, &k);
  47.         for (int i = 1; i <= n; ++i) {
  48.             scanf("%lld%lld", &a[i], &b[i]);
  49.         }
  50.         for (int i = 1; i <= n; ++i) {
  51.             scanf("%lld", &c[i]);
  52.         }
  53.         int L = -1, R = X;
  54.         //todo: binary search
  55.         while (R - L > 1) {
  56.             int mid = (L + R) / 2;
  57.             if (check(mid)) R = mid;
  58.             else L = mid;
  59.         }
  60.         if (R == X) R = -1;
  61.         printf("%d\n", R);
  62.     }
  63. }
  64.  
  65. //code 2
  66. #include <bits/stdc++.h>
  67. using namespace std;
  68.  
  69. int main () {
  70.     multiset<int> st;
  71.     st.insert(1);
  72.     cout << st.size() << endl;
  73.     cout << st.empty() << endl;
  74.     st.insert(1);
  75.     cout << st.size() << endl;
  76.     set<int>::iterator iter = st.find(3);
  77.     if (iter == st.end()) {
  78.         cout << "Not found" << endl;
  79.     }
  80.     else if (iter != st.end()) {
  81.         cout << "Found" << endl;
  82.     }
  83.     st.erase(1);
  84.     st.erase(st.find(1));
  85. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top