Submission #1239915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239915		damoon	Self Study (JOI22_ho_t2)	C++20	100 / 100	121 ms	5140 KiB

Main

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

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define B __int128
#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}

random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)

const int L = 3e5+10,mod = 1e9+7;
const B inf = 1000ll*1000*1000*1000*1000*1000+10;
ll n,m;
ll a[L],b[L];

B cei(B x,B y){
    return (x/y + (x%y != 0));
}

bool solve(B x){
    B sum = 0;
    for(int i=1;i<=n;i++){
        if(a[i]*m >= x)
            sum += ((B)a[i]*m-x)/a[i];
        else
            sum -= cei(x-a[i]*m,b[i]);
    }
    return (sum >= 0);
}

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }

    for(int i=1;i<=n;i++){
        a[i] = max(a[i],b[i]);
    }
    ll l=0,r=inf;
    while(r-l > 1){
        ll mid = (l+r)>>1;
        if(solve(mid))
            l = mid;
        else
            r = mid;
    }

    cout<<l<<endl;
}

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