Submission #1203437

#TimeUsernameProblemLanguageResultExecution timeMemory
1203437TriseedotSelf Study (JOI22_ho_t2)C++20
0 / 100
120 ms4936 KiB
// Made by ordinary newbie #pragma region setup #include <bits/stdc++.h> #include <random> #include <chrono> using namespace std; // variables #define int long long using ld = long double; using ll = long long; using ull = unsigned long long; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; // bitwise operations #define cnt_bit(n) __builtin_popcountll(n) #define low_bit(n) ((n) & (-(n))) #define bit(n, i) (((n) >> (i)) & 1) #define set_bit(n, i) ((n) | (1ll << (i))) #define reset_bit(n, i) ((n) & ~(1ll << (i))) #define flip_bit(n, i) ((n) ^ (1ll << (i))) // math #define sqr(n) ((n) * (n)) int log2_floor(ull n) { return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1; } const ll INF = 1e18; // utils #define len(x) (int) x.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template <typename T> istream& operator>>(istream& is, vector<T>& v) { for(auto& el : v) { is >> el; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < len(v); i++) { if (i) os << ' '; os << v[i]; } return os; } template<class... Args> auto create(size_t n, Args&&... args) { if constexpr(sizeof...(args) == 1) { return vector(n, args...); } else { return vector(n, create(args...)); } } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(pair<int, int> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM); } }; template<typename T, typename U> bool chmin(T& a, const U b) { if (b < a) { a = b; return true; } return false; } template<typename T, typename U> bool chmax(T& a, const U b) { if (b > a) { a = b; return true; } return false; } template<typename T> void compress(vector<T>& v) { int n = len(v); vector<pair<T, int>> u(n); for (int i = 0; i < n; i++) { u[i] = {v[i], i}; } sort(all(u)); int curr = 0; for (int i = 0; i < n; i++) { if (i != 0 && u[i].first != u[i - 1].first) curr++; v[u[i].second] = curr; } } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); #pragma endregion void solve() { int n, m; cin >> n >> m; vector<int> a(n), b(n); cin >> a >> b; int l = 0, r = INF; while (l + 1 < r) { int x = (l + r) / 2; int cnt = 0; for (int i = 0; i < n; i++) { int req = x; if (a[i] > b[i]) { if (a[i] * m >= req) { cnt += (req + a[i] - 1) / a[i]; req = 0; } else { req -= a[i] * m; cnt += m; } } cnt += (req + b[i] - 1) / b[i]; } if (cnt <= n * m) { l = x; } else { r = x; } } cout << l << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; for (int i = 1; i <= tt; i++) { 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...