Untitled
unknown
c_cpp
7 months ago
1.7 kB
5
Indexable
Never
#include <bits/stdc++.h> using namespace std; typedef long long ll; constexpr int SIZE = (1e+5); ll Items[SIZE]; ll L[SIZE]; int n; ll m; ll binary(ll target, ll level, ll items) { ll lo = 0, hi = target; while (lo <= hi) { ll mid = lo + (hi - lo) / 2; ll required_items = mid * (2 * level + mid - 1) / 2; if (required_items <= items) { lo = mid + 1; } else { hi = mid - 1; } } return hi; } void sol() { long long lo = 1; long long hi = (1e12); long long ans = -1; while (lo <= hi) { ll mid = lo + (hi - lo) / 2; ll cost = 0; ll tmp = m; bool can_make_triangle = true; for (int i = 0; i < n; i++) { if (mid > L[i]) { ll K = binary(mid - L[i], L[i], Items[i]) + L[i]; if (K < mid) { if (tmp >= (mid - K)){ tmp -= (mid - K); } else{ can_make_triangle = false; break; } } } else if (mid < L[i]) { can_make_triangle = false; break; } } if (can_make_triangle) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } if (ans > 0) { cout << ans << '\n'; } else { cout << "-1\n"; } } int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> L[i]; } for (int i = 0; i < n; i++) { cin >> Items[i]; } sol(); return 0; }