Submission #1183978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183978		jerzyk	Self Study (JOI22_ho_t2)	C++20	100 / 100	126 ms	5136 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll I = 1000000LL * 1000000LL * 1000000LL + 2LL;
const int N = 3 * 100 * 1000 + 7;
ll a[N], b[N];

ll Bal(ll m, int v, ll x)
{
    if(b[v] >= a[v])
        return m - ((x + b[v] - 1) / b[v]);
    if(m * a[v] >= x)
        return m - ((x + a[v] - 1) / a[v]);
    return -((x - a[v] * m + b[v] - 1) / b[v]);
}

bool Check(int n, ll m, ll x)
{
    ll l = 0;
    for(int i = 1; i <= n; ++i)
    {
        l += Bal(m, i, x);
        if(l < -I)
            return false;
    }
    return (l >= 0);
}

ll BS(int n, ll m)
{
    ll p = 0LL, k = I, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Check(n, m, s))
            p = s;
        else
            k = s - 1;
    }
    return p;
}

void Solve()
{
    int n; ll m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i)
        cin >> b[i];
    cout << BS(n, m) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}

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