Advertisement
Guest User

Untitled

a guest
Feb 19th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int const N = 1000000;
  5.  
  6. typedef int long long ll;
  7.  
  8. stack< pair<ll,ll> > a1;
  9. stack< pair<ll,ll> > a2;
  10.  
  11. ll dp[N];
  12.  
  13. ll n , t;
  14.  
  15. ll Pri[N];
  16. ll Time[N];
  17.  
  18. void add(ll x){
  19.  
  20.   ll mn = a1.empty() ? x : min(x,a1.top().second);
  21.   a1.push(make_pair(x,mn));
  22.  
  23. }
  24.  
  25. int mini(){
  26.  
  27.   ll mn;
  28.  
  29.   if( a1.empty() || a2.empty() ) mn = a1.empty() ? a2.top().second : a1.top().second;
  30.   else mn = min( a1.top().second , a2.top().second );
  31.   return mn;
  32.  
  33. }
  34.  
  35. void remove(){
  36.  
  37.   if(a2.empty()){
  38.  
  39.     while(!a1.empty()){
  40.  
  41.       ll ele = a1.top().first;
  42.       a1.pop();
  43.       ll mn = a2.empty() ? ele : min(ele,a2.top().second);
  44.       a2.push(make_pair(ele,mn));
  45.  
  46.     }
  47.  
  48.   }
  49.  
  50.   a2.pop();
  51.  
  52. }
  53.  
  54. bool func(ll r , ll tempo , ll fim){
  55.  
  56.   memset(dp,0,sizeof(dp));
  57.   for(int i = 1 ; i <= r ; i++) dp[i] = Time[i];
  58.    
  59.   for(int i = 0 ; i <= fim ; i++){
  60.  
  61.     if(a1.size() + a2.size() >= r + 1) remove();
  62.     if(i > r) dp[i] = mini() + Time[i];
  63.     add(dp[i]);
  64.  
  65.   }
  66.  
  67.   while(!a1.empty()) a1.pop();
  68.   while(!a2.empty()) a2.pop();
  69.  
  70.   for(int i = 1 ; i <= fim ; i++) dp[i] += i;
  71.  
  72.   if(dp[fim] <= tempo) return true;
  73.   else return false;
  74.  
  75. }
  76.  
  77. int bs(ll l , ll r , ll tempo){
  78.  
  79.   if(l == r) return l;
  80.  
  81.   ll mid = (l+r)/2;
  82.  
  83.   if(func(mid,tempo,n-1)) return bs(l,mid,tempo);
  84.  
  85.   else return bs(mid+1,r,tempo);
  86.  
  87. }
  88.  
  89. int main(){
  90.  
  91.   ifstream cin("journey.in");
  92.   ofstream cout("journey.out");
  93.  
  94.   cin >> n >> t;
  95.  
  96.   for(int i = 1 ; i <= n - 1 ; i++) cin >> Pri[i];
  97.   for(int i = 1 ; i <= n - 2 ; i++) cin >> Time[i];
  98.  
  99.   ll x = bs(1,n-1,t);
  100.   ll mn = 100000000;
  101.  
  102.   for(int i = x ; i <= n - 1 ; i++) mn = min(mn,Pri[i]);
  103.  
  104.   cout << mn << "\n";
  105.  
  106.   return 0;
  107.  
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement