fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 5e5;
  9.  
  10. int n, k, m, cnt[maxn + 10];
  11. ll a[maxn + 10], b, r;
  12.  
  13. bool check(ll val)
  14. {
  15.     memset(cnt, 0, sizeof cnt);
  16.     int ans = 0;
  17.     for (int i = 1; i <= n; i++)
  18.     {
  19.         ans += a[i] >= val;
  20.         int l = max(1, i - m + 1);
  21.         ll x = min(i * 1ll, (a[i] + b + i * r - val) / r);
  22.         if (x < l)
  23.             continue;
  24. //        cout << i << ' ' << l << ' ' << x, el;
  25.         cnt[l]++;
  26.         cnt[x + 1]--;
  27.     }
  28.     for (int i = 1; i <= n; i++)
  29.         cnt[i] += cnt[i - 1];
  30.     for (int i = 1; i <= m; i++)
  31.         ans -= a[i] >= val;
  32.     if (ans + cnt[1] >= k)
  33.         return 1;
  34.     for (int i = 1; i <= n - m; i++)
  35.     {
  36.         ans += a[i] >= val;
  37.         ans -= a[i + m] >= val;
  38. //        cout << i + 1 << ' ' << i + m << ' ' << ans << ' ' << cnt[i + 1], el;
  39.         if (ans + cnt[i + 1] >= k)
  40.             return 1;
  41.     }
  42.     return 0;
  43. }
  44. ll bs(ll l, ll r)
  45. {
  46.     ll ans = 0;
  47.     while (l <= r)
  48.     {
  49.         ll m = l + r >> 1;
  50.         if (check(m))
  51.         {
  52.             ans = m;
  53.             l = m + 1;
  54.         }
  55.         else
  56.             r = m - 1;
  57.     }
  58.     return ans;
  59. }
  60.  
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  64.     if (fopen("FERTILIZE.INP", "r"))
  65.     {
  66.         freopen("FERTILIZE.INP", "r", stdin);
  67.         freopen("FERTILIZE.OUT", "w", stdout);
  68.     }
  69.  
  70.     cin >> n >> k >> m >> b >> r;
  71.     for (int i = 1; i <= n; i++)
  72.         cin >> a[i];
  73.     cout << bs(0, 1e18);
  74. }
  75.  
Success #stdin #stdout 0.01s 5796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/U5ZbyF
language:
C++14 (gcc 8.3)
created:
9 hours 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!