fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define file "o"
  6. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  7. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  8. #define nl "\n"
  9. #define ss " "
  10. #define pb emplace_back
  11. #define fi first
  12. #define se second
  13. #define sz(s) (int)s.size()
  14. #define all(s) (s).begin(), (s).end()
  15. #define ms(a,x) memset(a, x, sizeof (a))
  16. #define cn continue
  17. #define re exit(0)
  18.  
  19. typedef __int128_t int128;
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=2e5+15;
  49. const int128 inf=2000000000000000005LL;
  50.  
  51. int n;
  52. int128 k, a[maxn];
  53.  
  54. inline bool check(int128 x)
  55. {
  56.     int128 cnt=0;
  57.     ff(i, 1, n) if(x>a[i])
  58.     {
  59.         int128 need=(x-a[i])/i;
  60.         if((int128)i*need+a[i]<x) ++need;
  61.         cnt+=need;
  62.     }
  63.     return cnt<=k;
  64. }
  65.  
  66. signed main()
  67. {
  68.     rf();
  69.     ll in_k;
  70.     cin>>n>>in_k; 
  71.     k=in_k;
  72.  
  73.     ff(i, 1, n) 
  74.     {
  75.         ll in_a; 
  76.         cin>>in_a; 
  77.         a[i]=in_a;
  78.     }
  79.  
  80.     int128 l=0, r=inf, ans=-1;
  81.     while(l<=r)
  82.     {
  83.         int128 mid=(l+r)>>1;
  84.         if(check(mid)) ans=mid, l=mid+1;
  85.         else r=mid-1;
  86.     }
  87.  
  88.     cout<<(long long)ans;
  89.     re;
  90. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
20 457
8 9 10 9 8 8 4 6 8 1 5 10 2 8 2 6 8 1 6 6
stdout
copy 
132
https://ideone.com/IbE8m0
language:
C++14 (gcc 8.3)
created:
1 hour 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!