제출 #1196509

#제출 시각아이디문제언어결과실행 시간메모리
1196509ofozSelf Study (JOI22_ho_t2)C++20
62 / 100
117 ms7492 KiB
#include <bits/stdc++.h> #define int unsigned long long using namespace std; bool is_possible(int x, const vector<int>& a, const vector<int>& b, const vector<int>& enum_order, int m) { int extra = 0; int n = a.size(); for (int i : enum_order) { int p = max(a[i], b[i]); if (b[i] >= a[i]) p = b[i]; else p = a[i]; int op = (x + p - 1) / p; // ceil(x / p) if (op <= m) { extra += (m - op); continue; } assert(x >= m * p); int needed = min(x - m * p, extra * (int)b[i]); op = (x - needed + p - 1) / p; if (op > m) return false; extra -= (needed + b[i] - 1) / b[i]; } return true; } void solve() { int n, m; cin >> n >> m; vector<int> a(n), b(n); for (int& ai : a) cin >> ai; for (int& bi : b) cin >> bi; vector<int> enum_order(n); for (int i = 0; i < n; ++i) enum_order[i] = i; sort(enum_order.begin(), enum_order.end(), [&](int i, int j) { return max(a[i], b[i]) > max(a[j], b[j]); }); int l = 0, r = numeric_limits<int>::max(); while (r - l > 1) { int mid = l + (r - l) / 2; if (is_possible(mid, a, b, enum_order, m)) l = mid; else r = mid; } cout << l << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...