Submission #995610

#	Time	Username	Problem	Language	Result	Execution time	Memory
995610		vysniak_grossmeister	Self Study (JOI22_ho_t2)	C++17	100 / 100	127 ms	5380 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const long long MAX = 2e18;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n, m;
    cin >> n >> m;

    ll a[n + 1];
    for(ll i = 1; i <= n; ++i){
        cin >> a[i];
    }

    ll b[n + 1];
    for(ll i = 1; i <= n; ++i){
        cin >> b[i];
    }

    ll L = 0;
    ll R = MAX;

    while(R - L > 1){

        ll mid = (L + R) >> 1;

        __int128 can = 0ll;

        __int128 need = 0ll;

        for(ll i = 1; i <= n; ++i){

             ll cur = (mid / max(a[i], b[i]) );

             if(mid % (max(a[i], b[i])) != 0) cur++;

             if(cur > m){

                cur -= ( (cur - m) );

                ll ost = (mid - (m * max(a[i], b[i]) ) );

                cur += (ost / b[i]);

                if((ost % b[i]) != 0ll) cur++;

             }

             if(cur < m){

                can += (m - cur);

             }
             if(cur > m){

                need += (cur - m);

             }

        }

        if(need <= can){
            L = mid;
        }
        else{
            R = mid;
        }

    }

    cout << L << endl;

    return 0;
    // 1000 * 1000 | 33 ?
}

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