JOI 2020/2021 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - 安全点検 (Safety Inspection)
僕が作成、提出したコードは、以下のとおりです。
/* 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; }