fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=500005;
  19. int n,k,h[MAX],low[MAX],high[MAX];
  20. ll t[MAX],prefix[MAX];
  21.  
  22. void pre()
  23. {
  24.     stack<int> st;
  25.     foru(i,1,n)
  26.     {
  27.         low[i]=1;
  28.         while(!st.empty() && h[st.top()]<h[i]) st.pop();
  29.         if(!st.empty()) low[i]=st.top();
  30.         st.push(i);
  31.     }
  32.     while(!st.empty()) st.pop();
  33.     ford(i,n,1)
  34.     {
  35.         high[i]=n;
  36.         while(!st.empty() && h[st.top()]<h[i]) st.pop();
  37.         if(!st.empty()) high[i]=st.top();
  38.         st.push(i);
  39.     }
  40.     while(!st.empty()) st.pop();   
  41. }
  42.  
  43. int maxR[MAX];
  44. bool check(ll x)
  45. {
  46.     memset(maxR,0,sizeof(maxR));
  47.     int l=1,r=1;
  48.     foru(i,1,n)
  49.     {
  50.         while(l<i && prefix[i]-prefix[l]>x)
  51.         {
  52.             ++l;
  53.         }
  54.         while(r<=n && prefix[r]-prefix[i]<=x)
  55.         {
  56.             ++r;
  57.         }
  58.         int L=max(l,low[i]), R=min(r-1,high[i]);
  59.         maxR[L]=max(maxR[L],R);
  60.     }
  61.     int need=1,cnt=0,i=1;
  62.     while(need<=n)
  63.     {
  64.         int mx=0;
  65.         while(i<=need)
  66.         {
  67.             mx=max(mx,maxR[i]);
  68.             ++i;
  69.         }
  70.         if(mx==0) break;
  71.         ++cnt;
  72.         need=mx+1;
  73.     }
  74.     return need>n && cnt<=k;
  75. }
  76.  
  77. int main()
  78. {
  79.     fastio
  80.     #ifndef ONLINE_JUDGE
  81.     freopen(FILE ".inp","r",stdin);
  82.     freopen(FILE ".out","w",stdout);
  83.     #endif // ONLINE_JUDGE
  84.  
  85.     cin>>n>>k;
  86.     foru(i,1,n) cin>>h[i];
  87.     foru(i,2,n) 
  88.     {
  89.         cin>>t[i];
  90.         prefix[i]=prefix[i-1]+t[i];
  91.     }
  92.     pre();
  93.     ll ans=-1,l=1,r=prefix[n];
  94.     while(l<=r)
  95.     {
  96.         ll m=(l+r)>>1;
  97.         if(check(m))
  98.         {
  99.             ans=m;
  100.             r=m-1;
  101.         }
  102.         else l=m+1;
  103.     }
  104.     cout<<ans;
  105.  
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/uAhiVe
language:
C++14 (gcc 8.3)
created:
6 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!