Submission #886585

#TimeUsernameProblemLanguageResultExecution timeMemory
886585ono_de206Self Study (JOI22_ho_t2)C++14
100 / 100
203 ms7624 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; // typedef pair<int, int> P; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T, typename U> istream & operator >> (istream &in, pair<T, U> &c) { in >> c.first; in >> c.second; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} const int mxn = 3e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523; const long long inf = 2e18 + 10; int a[mxn], b[mxn], x[mxn], n, m; bool check(int mid) { int mn = 0, mx = 0; for(int i = 1; i <= n; i++) { if(x[i] < mid) mn += (mid - x[i] + b[i] - 1) / b[i]; if(x[i] > mid) mx += (x[i] - mid) / a[i]; mnn(mn, inf); mnn(mx, inf); } return mn <= mx; } void go() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { cin >> b[i]; } int l = 1e18 + 10, r = 1e18 + 10; for(int i = 1; i <= n; i++) { mxx(a[i], b[i]); x[i] = a[i] * m; mnn(l, x[i]); } while(r - l > 1) { int mid = (l + r) / 2; if(check(mid)) l = mid; else r = mid; } cout << l << '\n'; } signed main() { fast; int t = 1; // cin >> t; while(t--) { go(); } 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...