Submission #983426

#	Time	Username	Problem	Language	Result	Execution time	Memory
983426		elitewantsyou	Self Study (JOI22_ho_t2)	C++14	64 / 100	237 ms	5656 KiB

Main

#include<bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define nl "\n"
#define int ll
typedef long long ll;
typedef long double ld;
using namespace std;
 
const int mod = 1e9 + 7;
const int N = 2000;
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--) {
        int n, m;
        cin >> n >> m;
        int a[n + 1], b[n + 1], mn = 1e18, mx = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mn = min( mn, a[i] * m);
            mx = max( mx, a[i] * m);
        }
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
            a[i] = max(a[i], b[i]);
        }
        if (m == 1) {
            int l = 1e18;
            for (int i = 1; i <= n; i++) {
                l = min( l, max(a[i], b[i]));
            }
            cout << l << nl;
        } else {
            int l = mn, r = mx + 1;
			int inf = 1e18;
            while(l + 1 < r) {
                int mid = (l + r) / 2;
                int s = 0;
                for (int i = 1; i <= n; i++) {
                    if (m >= (mid - 1) / a[i] + 1) {
                        //s += ((a[i] * m - mid) / a[i]);
                        s += (m - ((mid - 1) / a[i] + 1));
                    } else {
                        //s -= (mid - a[i] * m) / a[i];
                        int rem = mid - m * a[i];
                        s -= (rem - 1) / b[i] + 1;
                    }
                    if (abs(s) > inf) break;
                }
                if (s >= 0) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            cout << l << nl;
        }
    }
}

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