Submission #1199292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199292		kikikicem123	Self Study (JOI22_ho_t2)	C++20	0 / 100	309 ms	5008 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, m;
ll l = 0, r = 1e18, mid;
ll ceill(ll a, ll b) {return (a+b-1)/b;}

ll getsum(ll a, ll own, ll classi, ll mid) {
    ll b = ceill(mid - a*classi, own); b = max(b, 0ll);

    return a + b;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    vector<ll> a(n), b(n);
    for(ll &e:a) cin >> e;
    for(ll &e:b) cin >> e;
    for(int i=0;i<n;i++) a[i] = max(a[i], b[i]);

    while(l <= r) {
        mid = (l+r) >> 1;
        ll sum = 0;
        for(int i=0;i<n;i++) {
            //ll A = min(m, mid / a[i]);
            //ll res = ceill(A*(b[i] - a[i]) + mid, b[i]);
            ll res = min({getsum(0, b[i], a[i], mid), getsum(min(m, mid/a[i]), b[i], a[i], mid), getsum(min(m, mid/a[i]+1), b[i], a[i], mid)});
            res = min(res, getsum(min(m, max(0ll, mid/a[i]-1)), b[i], a[i], mid));
            sum += res;
            //cout << res << ' ';
        } //cout << '\n';
        //cout << mid << " -> " << sum << '\n';
        if(sum <= n*m) l = mid + 1;
        else r = mid - 1;
    }
    cout << r;
}

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