Submission #585784

#	Time	Username	Problem	Language	Result	Execution time	Memory
585784		Drew_	Self Study (JOI22_ho_t2)	C++17	100 / 100	292 ms	11500 KiB

Main

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 3e5 + 69;

ll n, m;
ll a[MAX], b[MAX];

#define ll __int128_t
inline bool check(ll val)
{
	ll sum = 0;
	for (int i = 0; i < n; ++i)
	{
		ll cur = val;
		if (a[i] > b[i])
		{
			ll attend = min((__int128_t)m, (cur + a[i] - 1) / a[i]);
			sum += attend;
			cur -= attend * a[i];
		}
		if (cur > 0) sum += (cur + b[i] - 1) / b[i];
	}

	return sum <= n*m;
}
#undef ll

int main()
{
	fastio;

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < n; ++i)
		cin >> b[i];

	ll l = 1, r = 1e18;
	while (l < r)
	{
		ll mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid-1;
	}

	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