Submission #1150978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150978		justkitkat	Self Study (JOI22_ho_t2)	C++17	0 / 100	131 ms	4936 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define show3(x,y,z) cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(n);
    for(auto &x:a)cin>>x;
    for(auto &x:b)cin>>x;
    int lo=1,hi=1e17;
    while(lo<hi){
        int mid=(lo+hi+1)/2; // min level is mid
        int over=0;
        for(int i=0;i<n;++i){
            // try to get a level of >= mid
            int take=0;
            if(a[i]>b[i]){ // if its better to go for the course
                take+=min(m,(mid-1)/a[i] + 1);
            }
            // cout<<take<<endl;
            int left=mid-take*a[i];
            if(left>0){
                // use as many b[i] to reach mid
                take+=((left-1)/b[i] + 1);
            }
            // cout<<take<<endl;
            over+=m-take;
        }
        // show3(mid,over,lo);
        if(over<0)hi=mid-1;
        else lo=mid;
    }
    cout<<lo;

}
// 27077044488345 (wrong)
// 41397427274960

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