Submission #1139894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139894		grizo	Self Study (JOI22_ho_t2)	C++20	100 / 100	175 ms	5136 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(v)                                                                 \
    cerr << "Line(" << __LINE__ << ") -> " << #v << " = " ; 
#define dbx(x) debug(x); cerr << x << "\n";
#define dbg(x) debug(x); cerr << "{ "; for(auto &e : x) cerr << e << ", "; cerr << "} \n";
#define log(x) (31^__builtin_clz(x))

const int N = 1e6+10, MOD = 1e9+7;

void solve(){

    int n, m; cin >> n >> m;
    vector<int> a(n); for(int i = 0 ; i < n ; i ++)cin >> a[i];
    vector<int> b(n); for(int i = 0 ; i < n ; i ++)cin >> b[i];

    auto check = [&](ll mid){
        ll _b = 0;
        vector<ll> cur(n);
        for(int i = 0 ; i < n ; i ++){
            if(b[i] >= a[i]){
                _b += m;
                cur[i] = mid;
                continue;
            }
            ll rt = mid / a[i] + (mid % a[i] > 0);
            rt = min(rt, (ll)m);
            _b += m - rt;
            cur[i] = mid - (rt * a[i]);
            cur[i] = max(cur[i], 0ll);
        }
        
        for(int i = 0 ; i < n ; i ++){
            ll rt = cur[i] / b[i] + (cur[i] % b[i] > 0);
            if(_b < rt){
                return false;
            }else {
                _b -= rt;
            }
        }
        return true;
    };

    ll l = 0, r = 2e18, ans = 0;
    while (l <= r)
    {
        ll mid = (l + r) / 2;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }else r = mid - 1;
    }

    cout << ans << "\n";

}
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // freopen("king2.in", "r", stdin);
    // freopen("king2.out", "w", stdout);

    int tc = 1; // cin >> tc;
    for(int t = 1 ; t <= tc ; t ++){
        solve();
    }
 
    return 0;
}
 
/*

*/

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