Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int const N = 1000000;
- typedef int long long ll;
- stack< pair<ll,ll> > a1;
- stack< pair<ll,ll> > a2;
- ll dp[N];
- ll n , t;
- ll Pri[N];
- ll Time[N];
- void add(ll x){
- ll mn = a1.empty() ? x : min(x,a1.top().second);
- a1.push(make_pair(x,mn));
- }
- int mini(){
- ll mn;
- if( a1.empty() || a2.empty() ) mn = a1.empty() ? a2.top().second : a1.top().second;
- else mn = min( a1.top().second , a2.top().second );
- return mn;
- }
- void remove(){
- if(a2.empty()){
- while(!a1.empty()){
- ll ele = a1.top().first;
- a1.pop();
- ll mn = a2.empty() ? ele : min(ele,a2.top().second);
- a2.push(make_pair(ele,mn));
- }
- }
- a2.pop();
- }
- bool func(ll r , ll tempo , ll fim){
- memset(dp,0,sizeof(dp));
- for(int i = 1 ; i <= r ; i++) dp[i] = Time[i];
- for(int i = 0 ; i <= fim ; i++){
- if(a1.size() + a2.size() >= r + 1) remove();
- if(i > r) dp[i] = mini() + Time[i];
- add(dp[i]);
- }
- while(!a1.empty()) a1.pop();
- while(!a2.empty()) a2.pop();
- for(int i = 1 ; i <= fim ; i++) dp[i] += i;
- if(dp[fim] <= tempo) return true;
- else return false;
- }
- int bs(ll l , ll r , ll tempo){
- if(l == r) return l;
- ll mid = (l+r)/2;
- if(func(mid,tempo,n-1)) return bs(l,mid,tempo);
- else return bs(mid+1,r,tempo);
- }
- int main(){
- ifstream cin("journey.in");
- ofstream cout("journey.out");
- cin >> n >> t;
- for(int i = 1 ; i <= n - 1 ; i++) cin >> Pri[i];
- for(int i = 1 ; i <= n - 2 ; i++) cin >> Time[i];
- ll x = bs(1,n-1,t);
- ll mn = 100000000;
- for(int i = x ; i <= n - 1 ; i++) mn = min(mn,Pri[i]);
- cout << mn << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement