Submission #1128435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128435		ByeWorld	Self Study (JOI22_ho_t2)	C++20	62 / 100	559 ms	7460 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 3e14+10;
const int MOD = 1e9+7;
const int LOG = 33;
const ld EPS = 1e-12;
void chmn(int &a, int b){ a = min(a, b); }
int sum(int a, int b){ return (a+b)%MOD; }
int mul(int a, int b){ return (1ll*a*b)%MOD; }
void chmul(int &a, int b){ a = (1ll*a*b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
int expo(int a, int b){
    a %= MOD;
    if(b==0) return 1;
    int te = expo(a,b/2); te=mul(te,te);
    return (b%2 ? mul(te, a) : te);
}

int n, m, a[MAXN], b[MAXN], sis[MAXN];

bool cek(int x){
    int need = 0, tot = 0;
    for(int i=1; i<=n; i++){
        int take = 0;
        if(a[i] > b[i]) take = min(m, (x+a[i]-1) / a[i] ); // 3e14
        tot += m-take; // n*m = 3e14
        sis[i] = max(0ll, x - take*a[i]); // 3e14
        // cout << i << ' ' << tot <<' '<<take<<' '<<sis[i] << " sis\n";

        if((need-tot)/m > (n-i)) return 0;

        int amb = (sis[i]+b[i]-1) / b[i]; // 3e14
        if((amb-tot)/m > (n-i) ) return 0;

        need += amb; // 3e14 * 3e5 = 9e19

        if((need-tot)/m > (n-i)) return 0;
    }
    return need <= tot;
}

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    int mn = INF;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];

    // cout << cek(23) << "cek\n";
    int l=0, r=INF, mid=0, cnt=0;
    while(l<=r){
        mid = md;
        if(cek(mid)) cnt = mid, l = mid+1;
        else r = mid-1;
    }
    cout << cnt << '\n';
}

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