Submission #625172

#	Time	Username	Problem	Language	Result	Execution time	Memory
625172		iomoon191	Self Study (JOI22_ho_t2)	C++17	100 / 100	655 ms	11460 KiB

Main

#include <bits/stdc++.h>
using ll = long long;
// #define int ll
using namespace std;

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353

#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

const ll N = 500005;
const ll inf = 1e18;

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

bool chk(ll x){
	ll res = 0;
	foru(i, 1, n){
		if(a[i] > b[i]){
			ll z = (x + a[i] - 1) / a[i];
			z = min(z, m);
			ll nw = inf;
			foru(j, max(z - 2, 0ll), z){
				ll rem = max(x - a[i] * j, 0ll);
				nw = min(nw, j + (rem + b[i] - 1) / b[i]);
			}
			res += nw;
		}
		else{
			res += (x + b[i] - 1) / b[i];
		}
		if(res > m * n) return false;
	}
	return true;
}

void solve(){
	cin >> n >> m;
	foru(i, 1, n) cin >> a[i];
	foru(i, 1, n) cin >> b[i];
	ll l = 0, r = inf;
	while(l != r){
		ll mid = (l + r + 1) >> 1;
		if(chk(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1; 
	while(t--){
		solve();
	}
}

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