Submission #640105

#	Time	Username	Problem	Language	Result	Execution time	Memory
640105		kdn5549	Self Study (JOI22_ho_t2)	C++17	100 / 100	648 ms	11464 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const ll INF=1e18;
const ll mod=1e9+7;

const int mxn=3e5+5;
ll a[mxn], b[mxn];
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    ll n, m; cin >> n >> m;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    auto chk=[&](ll x)
    {
        ll ret=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]<=b[i]) ret+=(x+b[i]-1)/b[i];
            else
            {
                ll cur=min(m, (x+a[i]-1)/a[i]);
                ll nw=INF;
                for(int j=max(cur-2, 0ll);j<=cur;j++)
                {
                    ll rem=max(x-a[i]*j, 0ll);
                    nw=min(nw, j+(rem+b[i]-1)/b[i]);
                }
                ret+=nw;
            }
            if(ret>m*n) return false;
        }
        return true;
    };
    ll lo=0, hi=INF;
    while(lo<hi)
    {
        ll m=(lo+hi+1)/2;
        if(chk(m)) lo=m;
        else hi=m-1;
    }
    
    cout << lo;
}

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