fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25.  
  26. //_ ***************************** START Below *******************************
  27.  
  28. // 3 7
  29. // 3 2 5
  30.  
  31.  
  32.  
  33. vector<int> a;
  34.  
  35.  
  36. bool isPossible(int n, int k, int mid){
  37.     int p = 0;
  38.     for(int i=0; i<n; i++){
  39.         p += (mid/a[i]);
  40.  
  41.         //_ Stop early to pkrevent overflow 
  42.         if(p >= k) return true;
  43.     }
  44.  
  45.     return p>=k;
  46. }
  47.  
  48.  
  49. int consistency1(int n, int k){
  50.  
  51. 	int mini = LINF;
  52. 	for(int i=0; i<n; i++) mini = min(mini, a[i]);
  53.  
  54.     int s = mini, e = k*mini;
  55.     int ans = LINF;
  56.  
  57.     while(s<=e){
  58.         int mid = s + (e-s)/2;
  59.         if(isPossible(n, k, mid)){
  60.             ans = min(ans, mid);
  61.             e = mid-1;
  62.         }
  63.         else s = mid+1;
  64.     }
  65.  
  66.     return ans;
  67.  
  68. }
  69.  
  70.  
  71.  
  72.  
  73. int consistency2(int n, int k){
  74.  
  75. 	int mini = LINF;
  76. 	for(int i=0; i<n; i++) mini = min(mini, a[i]);
  77.  
  78. 	int s = mini;
  79. 	int e = k*mini;
  80.  
  81. 	while(s<e){
  82. 		int mid = s + (e-s)/2;
  83. 		if(isPossible(n, k, mid)){
  84. 			e = mid;
  85. 		}
  86. 		else s = mid+1;
  87. 	}
  88.  
  89. 	return e;
  90.  
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101. int practice(int n, int k){
  102.  
  103.  
  104. }
  105.  
  106.  
  107.  
  108.  
  109.  
  110. void solve() {
  111.  
  112.     int n, k;
  113.     cin>>n >> k;
  114.  
  115.     a.resize(n);
  116.  
  117.     for(int i=0; i<n; i++) cin >> a[i];
  118.  
  119.     cout << consistency2(n, k) << endl;
  120.     // cout << consistency2(n, k) << " -> " << practice(n,k) << endl;
  121.  
  122.  
  123. }
  124.  
  125.  
  126.  
  127.  
  128.  
  129. int32_t main() {
  130.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  131.  
  132.     int t = 1;
  133.     // cin >> t;
  134.     while (t--) {
  135.         solve();
  136.     }
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 7
3 2 5
stdout
copy 
8
https://ideone.com/gdQDZQ
language:
C++14 (gcc 8.3)
created:
2 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!