Submission #593547

#	Time	Username	Problem	Language	Result	Execution time	Memory
593547		oleh1421	Self Study (JOI22_ho_t2)	C++17	100 / 100	229 ms	5244 KiB

Main

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
#define endl '\n'
#define int ll
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=600010;
const int Lg=16;
ll a[N],b[N];
ll n,m;
bool ok(ll D){
    ll sum=0ll;
    for (int i=1;i<=n;i++){
        if (a[i]*m>=D){
            sum+=m-(D+a[i]-1)/a[i];
        } else {
            sum-=(D-a[i]*m+b[i]-1)/b[i];
        }
        if (sum+n*m<0) return false;
    }
    return (sum>=0);
}
void solve(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) cin>>b[i];
    for (int i=1;i<=n;i++) a[i]=max(a[i],b[i]);
    ll ans=0ll;
    for (ll i=60;i>=0;i--){
        if (ok(ans+(1ll<<i))) ans+=(1ll<<i);
    }
    cout<<ans<<endl;

}
int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

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