fork download
copy 
  1. // template taken from Striver_79
  2. // Remember you were also a novice when you started
  3. // hence never be rude to anyone who wants to learn something
  4. // Never open a ranklist untill and unless you are done with solving problems, wastes 3/4 minuts
  5. // Donot treat CP as a placement thing, love it and enjoy it, you will succeed for sure.
  6. // The goal is to solve problems most efficiently not just barely
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <string>
  14. #include <iostream>
  15. #include <algorithm>
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18. typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  19. const int mod = 1e9 + 7;
  20. #define int long long
  21. typedef long long ll;
  22. typedef vector<ll> vi;
  23. typedef vector<vector<int>> vii;
  24. typedef vector<pair<int, int>> vpi;
  25. typedef pair<int, int> pi;
  26. void myerase(ordered_set &t, int v)
  27. {
  28.     int rank = t.order_of_key(v);                     // Number of elements that are less than v in t
  29.     ordered_set::iterator it = t.find_by_order(rank); // Iterator that points to the (rank+1)th element in t
  30.     t.erase(it);
  31. }
  32. int power(long long x, unsigned int y, int p = 1e9 + 7)
  33. {
  34.     int res = 1; // Initialize result
  35.  
  36.     x = x % p; // Update x if it is more than or
  37.                // equal to p
  38.  
  39.     if (x == 0)
  40.         return 0; // In case x is divisible by p;
  41.  
  42.     while (y > 0)
  43.     {
  44.         // If y is odd, multiply x with result
  45.         if (y & 1)
  46.             res = (res * x) % p;
  47.  
  48.         // y must be even now
  49.         y = y >> 1; // y = y/2
  50.         x = (x * x) % p;
  51.     }
  52.     return res;
  53. }
  54.  
  55. // C function for extended Euclidean Algorithm (used to
  56. // find modular inverse.
  57. int gcdExtended(int a, int b, int *x, int *y)
  58. {
  59.     // Base Case
  60.     if (a == 0)
  61.     {
  62.         *x = 0, *y = 1;
  63.         return b;
  64.     }
  65.  
  66.     int x1, y1; // To store results of recursive call
  67.     int gcd = gcdExtended(b % a, a, &x1, &y1);
  68.  
  69.     // Update x and y using results of recursive
  70.     // call
  71.     *x = y1 - (b / a) * x1;
  72.     *y = x1;
  73.  
  74.     return gcd;
  75. }
  76.  
  77. int modInverse(int b, int m)
  78. {
  79.     int x, y; // used in extended GCD algorithm
  80.     int g = gcdExtended(b, m, &x, &y);
  81.  
  82.     // Return -1 if b and m are not co-prime
  83.     if (g != 1)
  84.         return -1;
  85.  
  86.     // m is added to handle negative x
  87.     return (x % m + m) % m;
  88. }
  89.  
  90. // Function to compute a/b under modulo m
  91. int modDivide(int a, int b, int m)
  92. {
  93.     a = a % m;
  94.     int inv = modInverse(b, m);
  95.     if (inv == -1)
  96.         return -1;
  97.     else
  98.         return (inv * a) % m;
  99. }
  100. ll accurateFloor(ll a, ll b)
  101. {
  102.     ll val = a / b;
  103.     while (val * b > a)
  104.         val--;
  105.     return val;
  106. }
  107. bool check(long long mid, vector<int> &arr, int m)
  108. {
  109.     long long s = 0;
  110.     int start = 0;
  111.     int n = arr.size();
  112.     long long prev = 0;
  113.  
  114.     for (int i = 0; i < n;)
  115.     {
  116.         int point = arr[i] - arr[start];    
  117.         if ((s + point )> mid)
  118.         {
  119.             m--;
  120.             s += prev;
  121.             prev = 0;
  122.             start = i;
  123.         }
  124.         else
  125.         {
  126.             prev = point;
  127.             i++;
  128.         }
  129.     }
  130.     return m > 0;
  131. }
  132.  
  133. void solve()
  134. {
  135.     // Do not get stuck on a single approach for long, think of multiple ways
  136.     ll n;
  137.     cin >> n;
  138.     ll m;
  139.     cin >> m;
  140.     vi arr(n, 0);
  141.     for (int i = 0; i < n; i++)
  142.     {
  143.         cin >> arr[i];
  144.     }
  145.     sort(arr.begin(),arr.end());
  146.     if(m==n)
  147.     {
  148.         cout<<"0\n";
  149.         return;
  150.     }
  151.     int lo=0;
  152.     int hi=1e18;
  153.     int ans=1e18;
  154.     while(lo<=hi)
  155.     {
  156.         int mid=(lo+hi)/2;
  157.         if(check(mid,arr,m))
  158.         {
  159.             ans=mid;
  160.             hi=mid-1;
  161.         }
  162.         else
  163.         {
  164.             lo=mid+1;
  165.         }
  166.     }
  167.     cout<<ans<<"\n";
  168. }
  169. int32_t main()
  170. {
  171.     // hamare saath shree raghunath to kisi baat ki chinta nahi
  172.     ios_base::sync_with_stdio(false);
  173.     cin.tie(NULL);
  174.     int t = 1;
  175.     // cin >> t;
  176.     while (t--)
  177.     {
  178.         solve();
  179.     }
  180.     return 0;
  181. }
Runtime error #stdin #stdout #stderr 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/8Vi71u
language:
C++14 (gcc 8.3)
created:
213 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!