Submission #696221

#	Time	Username	Problem	Language	Result	Execution time	Memory
696221		Deepesson	Self Study (JOI22_ho_t2)	C++17	100 / 100	387 ms	16056 KiB

Main

#include <bits/stdc++.h>
#define MAX 305000

using ll = long long;
__int128 A[MAX],B[MAX];
__int128 N,M;

__int128 teto(__int128 a,__int128 b){
    ll c = a/b;
    if(a%b)++c;
    return c;
}

bool possivel(__int128 x){
    __int128 sum=0;
    for(int i=0;i!=N;++i){
        __int128 necessario = teto(x,A[i]);
        __int128 gastar = std::min(necessario,M);
        __int128 falta = x-(gastar*A[i]);
        if(falta>0){
            ll precisa = teto(falta,B[i]);
            sum-=precisa;
        }else {
            ll sobra = M-gastar;
            sum+=sobra;
        }
    }
    return sum>=0;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll a,b;
    std::cin>>a>>b;N=a;M=b;
    for(int i=0;i!=N;++i){long long x;std::cin>>x;A[i]=x;}
    for(int i=0;i!=N;++i){long long x;std::cin>>x;B[i]=x;}
    for(int i=0;i!=N;++i){
        if(A[i]<B[i]){
            A[i]=B[i];
        }
    }

    __int128 l=1,r=1LL<<60LL;
    while(l<r){
        __int128 m=((r-l+1)/2)+l;
        if(possivel(m)){
            l=m;
        }else r=m-1;
    }
    std::cout<<(ll)l<<"\n";
}

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