Submission #650084

#	Time	Username	Problem	Language	Result	Execution time	Memory
650084		TheEvilBird	Self Study (JOI22_ho_t2)	C++17	100 / 100	264 ms	11464 KiB

Main

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#ifdef __APPLE__

#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif

void solve() {
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        a[i] = max(a[i], b[i]);
    }
    ll l = 0, r = 2e18;

    auto check = [&](ll md) -> bool {
        ll days = 0;
        for (int i = 0; i < n; ++i) {
            if (m * a[i] >= md) {
                days += (md + a[i] - 1) / a[i];
            }
            else {
                ll musor = md - a[i] * m;
                days += m;
                days += (musor + b[i] - 1) / b[i];
            }
            if (days > 1LL * n * m) {
                return false;
            }
        }
        return days <= 1LL * n * m;
    };

    while (r - l > 1) {
        ll md = l + (r - l) / 2;
        if (check(md)) {
            l = md;
        } else {
            r = md;
        }
    }
    cout << l << en;
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9