Submission #1110764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110764		Flandre	Self Study (JOI22_ho_t2)	C++17	100 / 100	103 ms	11592 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

// loal is the cutest girl

#define ll long long
#define int ll
#define ld long double
#define pow2(x) (x)*(x)
#define le left
#define ri right
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
#define isvowel(x) (x) == 'a' || (x) == 'i' || (x) == 'u' || (x) == 'e' || (x) == 'o'
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ld EPS = 1e-9;
const ld PI = 3.141592653589793238462643383279502884197169399375105820974944;

const int maxn = 3e5+5;
int n, m;
int a[maxn];
int b[maxn];

bool solve(ll amo) {
  ll needed = 0;
  for (int i = 0; i < n; i++) {
    if (a[i]*m >= amo) {
      needed += (amo+a[i]-1)/a[i];
    } else {
      needed += m+(amo-a[i]*m+b[i]-1)/b[i];
    }
    if (needed > n*m) return false;
  }
  return true;
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    a[i] = max(a[i], b[i]);
  }

  ll l = 1, r = 1e18;

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

  // solve(18);

  // for (int i = 0; ; i++) if (!solve(i)) {
  //   cout << i-1;
  //   return 0;
  // }

  cout << l << '\n';

  return 0;
}

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