Submission #1181135

#TimeUsernameProblemLanguageResultExecution timeMemory
1181135anteknneSelf Study (JOI22_ho_t2)C++20
0 / 100
193 ms7484 KiB
#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; typedef long long ll; typedef long double ld; #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug false const int MAXN = 300 * 1000; ll a[MAXN]; ll t[MAXN]; ll b[MAXN]; ll m; ll n; ll dziel (ll a, ll b) { return (a/b + (a % b != 0LL)); } bool ok (ll d) { ll ile = 0LL; ll m2 = m * n; for (ll i = 0; i < n; i ++) { t[i] = d; } for (ll i = 0; i < n; i ++) { if (b[i] >= a[i]) { continue; } ile += min(m, dziel(d, a[i])); t[i] -= min(m, dziel(d, a[i])) * a[i]; } for (ll i = 0; i < n; i ++) { if (t[i] > 0LL) { ile += dziel(t[i], b[i]); } } /*cout << ile << "\n"; for (int i = 0; i < n; i ++) { cout << t[i] << " "; } cout << "\n";*/ return (ile <= ll(n) * m); } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (ll i = 0; i < n; i ++) { cin >> a[i]; } for (ll i = 0; i < n; i ++) { cin >> b[i]; } ll p = 0LL, k = LLONG_MAX/3LL, wyn; while (p <= k) { ll sr = (p + k)/ 2LL; if (ok(sr)) { wyn = sr; p = sr + 1LL; } else { k = sr - 1LL; } } //cout << ok(8) << "\n"; cout << wyn << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...