fork download 
  1. #include <cstdio>
  2. #include <queue>
  3. #include <set>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n,m;
  8. int gs[40005];
  9. int gf[40005];
  10. int rp[40005];
  11. int dp[40005];
  12. multiset<int> s;
  13.  
  14. void pop_back(deque<int>& u){
  15.     if(u.size()>1) s.erase(s.find(dp[u[u.size()-2]+1]+rp[u.back()]));
  16.     u.pop_back();
  17. }
  18.  
  19. void pop_front(deque<int>& u){
  20.     if(u.size()>1) s.erase(s.find(dp[u.front()+1]+rp[u[1]]));
  21.     u.pop_front();
  22. }
  23.  
  24. bool gao(int top){
  25.     s.clear();
  26.     deque<int> u;
  27.     for(int i=0,j=0;i<n;i++){
  28.         while(gs[i+1]-gs[j]>top) j++;
  29.         while(u.size() && u.front()<j) pop_front(u);
  30.         while(u.size() && rp[u.back()]<=rp[i]) pop_back(u);
  31.         u.push_back(i);
  32.         if(u.size()>1) s.insert(dp[u[u.size()-2]+1]+rp[u.back()]);
  33.         dp[i+1]=rp[u.front()]+dp[j];
  34.         if(s.size()) dp[i+1]=min(*s.begin(),dp[i+1]);
  35.     }
  36.     return dp[n]<=m;
  37. }
  38.  
  39. int main(){
  40.     while(scanf("%d%d",&n,&m)==2){
  41.         for(int i=0;i<n;i++){
  42.             scanf("%d%d",rp+i,gf+i);
  43.             gs[i+1]=gs[i]+gf[i];
  44.         }
  45.         int lo=*max_element(gf,gf+n),hi=gs[n];
  46.         while(lo<hi){
  47.             int x=(lo+hi)/2;
  48.             if(gao(x)) hi=x; else lo=x+1;
  49.         }
  50.         printf("%d\n",lo);
  51.     }
  52. }
  53.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PmNCio
language:
C++ (gcc 8.3)
created:
12 years 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!