fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "test"
  5.  
  6. #define ll long long
  7. #define fi first
  8. #define sc second
  9. #define ii pair <int, int>
  10.  
  11. #define rep(i,s,e) for (int i = (s), _e = (e); i <= _e; i++)
  12. #define reo(i,s,e) for (int i = (s), _e = (e); i >= _e; i--)
  13.  
  14. const int maxn = 5e5 + 5;
  15. const int mod = 1e9 + 7;
  16. const ll inf = 1e15;
  17.  
  18. int n, k;
  19. int h[maxn]; ll s[maxn];
  20. int L[maxn], R[maxn];
  21.  
  22. void build ()
  23. {
  24.     stack <int> st;
  25.     rep (i, 1, n)
  26.     {
  27.         while (!st.empty() and h[st.top()] < h[i]) st.pop();
  28.         L[i] = st.empty() ? 1 : st.top();
  29.         st.push(i);
  30.     }
  31.  
  32.     while (!st.empty()) st.pop();
  33.     reo (i, n, 1)
  34.     {
  35.         while (!st.empty() and h[st.top()] < h[i]) st.pop();
  36.         R[i] = st.empty() ? n : st.top();
  37.         st.push(i);
  38.     }
  39. }
  40.  
  41. bool check (ll x)
  42. {
  43.     vector <int> maxReach(n + 1, -1);
  44.     for (int i = 1, l = 0, r = 0; i <= n; i++)
  45.     {
  46.         if (r < i) r = i;
  47.         while (l <= n and s[i] - s[l] > x) l++;
  48.         while (r + 1 <= n and s[r + 1] - s[i] <= x) r++;
  49.  
  50.         int a = max(L[i], l);
  51.         int b = min(R[i], r);
  52.  
  53.         if (a <= b) maxReach[a] = max(maxReach[a], b);
  54.     }
  55.  
  56.     rep (i, 1, n) maxReach[i] = max(maxReach[i], maxReach[i - 1]);
  57.  
  58.     for (int i = 1, cnt = 0; i <= n; i = maxReach[i] + 1)
  59.     {
  60.         if (maxReach[i] == -1) return false;
  61.         if (++cnt > k) return false;
  62.     }
  63.     return true;
  64. }
  65.  
  66. signed main ()
  67. {
  68.     cin.tie(0)->sync_with_stdio(false);
  69.     #ifndef ONLINE_JUDGE
  70.     freopen(TASK".inp","r",stdin);
  71.     freopen(TASK".out","w",stdout);
  72.     #endif
  73.  
  74.     cin >> n >> k;
  75.     rep (i, 1, n) cin >> h[i];
  76.     rep (i, 2, n) cin >> s[i], s[i] += s[i - 1];
  77.  
  78.     build();
  79.  
  80.     ll l = 0, r = s[n], res = -1;
  81.  
  82.     while (l <= r)
  83.     {
  84.         ll mid = l + r >> 1;
  85.         if (check(mid)) r = (res = mid) - 1;
  86.         else l = mid + 1;
  87.     }
  88.     cout << res << '\n';
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/OdzaZf
language:
C++14 (gcc 8.3)
created:
14 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!