Submission #915452

#	Time	Username	Problem	Language	Result	Execution time	Memory
915452		HorizonWest	Self Study (JOI22_ho_t2)	C++17	100 / 100	398 ms	16284 KiB

Main

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

#define int long long

#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

long long Max = 1e6 + 7, Inf = 2e18;

void print(bool x) { cout << (x ? "Yes" : "No") << endl; }

int ans = 0;

bool can(vector <int> &a, vector <int> &b, vector <int> &c, int x)
{ //  cout << x << endl;
    int win = 0LL, lose = 0LL, n = (int) c.size();

    vector <int> r(n);

    for(int i = 0; i < n; i++)
    {
        int v = abs(c[i] - x);

        if(c[i] > x)
        {
            r[i] = c[i] - a[i] * (v / a[i]);
            win = win + abs((int) v / a[i]);
        }

        if(c[i] < x)
        {
            r[i] = c[i] + b[i] * (v/b[i] + ((v%b[i]) != 0));
            lose = lose + abs((int) v / b[i]) + abs((int) ((v%b[i]) != 0));
        }
/*
        if(win > lose) { win -= lose; lose = 0; }
        if(lose > win) { lose -= win; win = 0; }*/

        if(lose > Inf || win > Inf) return false;

        if(c[i] == x) r[i] = c[i];
    }

    bool op = true;

    if(win >= lose)
    {
        //cout << x << endl;
        int temp = Inf;
        for(int i = 0; i < n; i++)
        {
           // cout << r[i] << endl;
             if(r[i] < x) op = false;
             temp = min(temp, r[i]);
        }
       // cout << temp << endl;
        ans = max(ans, temp);
        return op;
    }
    else
        return false;


    return win >= lose;
}

/*
3 3
19 4 5
2 6 2

4 25
1 2 3 4
1 2 3 4
*/

void solve()
{
    int n, m; cin >> n >> m;
    vector <int> a(n), b(n), c(n);
    for(auto& u : a) cin >> u;
    for(auto& u : b) cin >> u;

    int rx = Inf;

    for(int i = 0; i < n; i++)
    {
        a[i] = max(a[i], b[i]);
        c[i] = a[i] * m;
        rx = min(rx, c[i]);
    }

    if(m == 1)
    {
        cout << rx << endl;
        return;
    }

    int l = 0, r = Inf;

    while(abs(l - r) != 1)
    {
        int middle = (l + r) / 2;

        if(can(a, b, c, middle))
            l = middle;
        else
            r = middle;
    }

/*
    for(int i = max(1LL, l - 10LL); i < l + 10LL; i++)
        if(can(a, b, c, i)) l = i;*/

    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

   // freopen("02-18.in", "r", stdin);
   // freopen("output.txt", "w", stdout);

    int Q = 1; //cin >> Q;

    while(Q--)
    {
        solve();
    }

    return 0;
}

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