Submission #1249336

#TimeUsernameProblemLanguageResultExecution timeMemory
1249336norman165Self Study (JOI22_ho_t2)C++20
0 / 100
1095 ms23924 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long #define yes() cout << "YES\n" #define no() cout << "NO\n" using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 1e7 + 5e6; const int mod1 = 998244353; const int mod2 = 1e18 + 1; const int mod3 = 1e9 + 9; const int mod4 = 333333333; const int mod5 = 200000; const int mod6 = 10007; const int k = 300; const int w = 1e5; const ld EPS = 1e-8; int LOG = 30; void solve() { int n, m; cin >> n >> m; vector<int> a(n), b(n); for (int& i : a) cin >> i; for (int& i : b) cin >> i; int l = 0; int r = 1e14; auto check = [&](int x) { vector<int> prime(n), cnt(n, m); for (int i = 0; i < n; i++) { int y = max(a[i], b[i]); int c = min(m, (x + y - 1) / y); cnt[i] -= c; prime[i] += c * y; } set<int> need; multiset<int> free; for (int i = 0; i < n; i++) if (prime[i] < x) need.insert(i); for (int i = 0; i < n; i++) if (cnt[i] > 0) free.insert(cnt[i]); while (need.size() && free.size()) { int i = *need.begin(); int y = b[i]; int must = x - prime[i]; int gol = (must + y - 1) / y; while (free.size() && gol > 0) { int much = *free.begin(); free.extract(much); if (gol < much) { much -= gol; gol = 0; } else { gol -= much; much = 0; } if (much > 0) free.insert(much); } if (gol == 0) need.erase(need.begin()); else break; } return need.empty(); }; while (r - l > 1) { int mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } cout << l << "\n"; } signed main() { // cout.precision(16); ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } }
#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...