寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #D - 安全点検 (Safety Inspection)

JOI 2020/2021 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#D - 安全点検 (Safety Inspection)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#D - 安全点検 (Safety Inspection)
https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_d
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k;
ll a[100001],b[100001];
bool tf(ll x){
  ll per=k;
  ll ne,rem=0;
  for(ll i=n-1;i>=0;i--){
    if(rem>=b[i]){
      rem-=b[i];
      continue;
    }
    ll work=b[i]-rem;
    ll num=x-a[i];
    if(num<=0){
      return 0;
    }
    ne=work/num;
    if(work%num!=0){
      ne++;
    }
    rem=ne*num-work;
    per-=ne;
    if(per<0){
      return false;
    }
  }
  return true;
}
int main(void){
  cin>>n>>k;
  for(ll i=0;i<n;i++){
    cin>>a[i];
  }
  for(ll i=0;i<n;i++){
    cin>>b[i];
  }
  ll l=0,r=(1LL<<60),mid;
  while(l<=r){
    mid=((r-l)>>1)+l;
    if(tf(mid)){
      r=mid-1;
    }else{
      l=mid+1;
    }
  }
  cout<<l<<endl;
  return 0;
}