Submission #532401

#	Time	Username	Problem	Language	Result	Execution time	Memory
532401		Marceantasy	Self Study (JOI22_ho_t2)	C++17	100 / 100	636 ms	11340 KiB

Main

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

#define ll long long 
#define ar array

const int mxN = 3e5+5, M = 1e9+7;
ll n, m, a[mxN], b[mxN];

bool f(ll val){
    ll ret = 0;
    for(int i = 0; i<n; ++i){
        if(a[i] <= b[i]){
            ret += (val+b[i]-1)/b[i];
        }
        else{
            ll flag = (val+a[i]-1)/a[i];
            flag = min(flag, m);
            ll upd = 1e18;
            for(ll j = max(flag-2, 0ll); j<=flag; ++j){
                ll rem = max(0ll, val - a[i]*j);
                upd = min(upd, j + (rem+b[i]-1)/b[i]);
            }
            ret += upd;
        }
        if(ret > n*m) return 0;
    }
    return 1;

}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i<n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i<n; ++i){
        cin >> b[i];
    }
    ll l = 0, r = 1e18; 
    while(l != r){
        ll m = (l+r+1)/2;
        if(f(m)){
            l = m; 
        }else{
            r = m-1;
        }
    }
    cout << l;
}

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