Submission #1267645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267645		julia_08	Self Study (JOI22_ho_t2)	C++20	100 / 100	136 ms	5132 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 3e5 + 10;
const ll INF = 1e18;

ll a[MAXN], b[MAXN];

ll n, m;

bool check(ll x){

  ll cnt = 0;

  for(int i=1; i<=n; i++){

    if(b[i] >= a[i]){
      
      cnt += (x + b[i] - 1) / b[i];

    } else{

      ll cur = min(m, (x + a[i] - 1) / a[i]);

      ll left = max(0LL, x - cur * a[i]);
      cur += (left + b[i] - 1) / b[i];

      cnt += cur;

    } 

    if(cnt > n * m) return false;

  }

  return cnt <= n * m;

}

ll bs(){

  ll l = 0, r = INF;

  while(l < r){
    ll m = l + (r - l + 1) / 2;
    if(check(m)) l = m;
    else r = m - 1;
  }

  return l;

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  for(int i=1; i<=n; i++) cin >> a[i];

  for(int i=1; i<=n; i++) cin >> b[i];

  cout << bs() << "\n";

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9