• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<cmath>
3. #include<algorithm>
4. #include<vector>
5.
6. using namespace std;
7. using ll = long long;
8. using ull = unsigned long long;
9. ull mid = 0;
10.
11. struct jewel{
12.     ull id;
13.     ull v;
14.     ull w;
15. };
16.
17. bool comp(jewel a1, jewel a2){
18.     return ((a1.v - mid * a1.w) < (a2.v - mid * a2.w));
19. }
20.
21.
22. int main() {
23.     ios_base::sync_with_stdio(false);
24.     cin.tie(nullptr);
25.
26.     ull n, k;
27.     cin >> n >> k;
28.
29.     vector<jewel> vec(n);
30.
31.     cin >> vec[0].v >> vec[0].w;
32.     vec[0].id = 0;
33.
34.     ull max = vec[0].v;
35.     ull min = vec[0].w;
36.
37.     for(ull i = 1; i < n; ++i){
38.         cin >> vec[i].v >> vec[i].w;
39.         vec[i].id = i;
40.         if (vec[i].v > max) max = vec[i].v;
41.         if (vec[i].w < min) min = vec[i].w;
42.     }
43.
44.     //диапазоны бин поиска, идем по ответу
45.
46.     ull l = 0; //включая
47.     ull r = max / min + 1; //не включая
48.     ull sum = 0;
49.
50.     while(r - l > 1){
51.         mid = (l + r) / 2;
52.         sort(vec.begin(), vec.end(), comp);
53.         for(ull i = n - k; i < n; ++i){
54.             sum += vec[i].v - mid * vec[i].w;
55.         }
56.         if (sum < 0) l = mid + 1;
57.         else r = mid;
58.         sum = 0;
59.     }
60.
61.     cout << mid;
62.
63.
64.     return 0;
65. }
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.

Top