Submission #900571

#	Time	Username	Problem	Language	Result	Execution time	Memory
900571		LinkedArray	Self Study (JOI22_ho_t2)	C++17	100 / 100	210 ms	11716 KiB

Main

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

using ll = long long;
#define int ll

#define pb push_back

const int MAX_N = 3e5;

int a[MAX_N + 5], b[MAX_N + 5];

bool check (int mij, int n, int m) {
	int i, sum, val, num_curs;
	
	sum = i = 0;
	num_curs = m * n;
	
	while (i < n && sum <= num_curs) {
		val = max(a[i], b[i]);
		
		sum++;
		if (val * m >= mij) {
			sum += ((mij - 1) / val);
		} else {
			if (val == b[i]) {
				sum += ((mij - 1) / b[i]);
			} else {
				sum += (m + (mij - val * m - 1) / b[i]);
			}
		}
		i++;
	}
	
	return (sum <= num_curs);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	
	int n, m, i, st, dr, mij;
	
	cin >> n >> m;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	for (i = 0; i < n; i++) {
		cin >> b[i];
	}
	
	st = 0, dr = LLONG_MAX;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (check(mij, n, m)) {
			st = mij + 1;
		} else {
			dr = mij - 1;
		}
	}
	
	cout << (st == 0 ? 0 : st - 1);
    return 0;
}

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