Submission #895405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895405	2023-12-29T21:36:02 Z	juliany2	Self Study (JOI22_ho_t2)	C++17	0 / 100	427 ms	10948 KB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 3e5 + 7;
int n;
ll m, a[N], b[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    ll lo = 1, hi = 1e18;
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;

        ll need = 0;
        for (int i = 1; i <= n; i++) {
            if (b[i] >= a[i])
                need += (mid + b[i] - 1) / b[i];
            else {
                ll take = min(m, (mid + a[i] - 1) / a[i]);
                need += take + (max(mid - take * a[i], 0LL) + b[i] - 1) / b[i];
            }
        }

        if (need <= m * n)
            lo = mid;
        else
            hi = mid - 1;
    }

    cout << lo << '\n';

    return 0;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	194 ms	10936 KB	Output is correct
12	Correct	191 ms	10948 KB	Output is correct
13	Correct	131 ms	8952 KB	Output is correct
14	Incorrect	427 ms	8952 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2512 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	76 ms	7628 KB	Output is correct
10	Correct	49 ms	6660 KB	Output is correct
11	Correct	37 ms	5980 KB	Output is correct
12	Correct	29 ms	5880 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	5 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	194 ms	10936 KB	Output is correct
12	Correct	191 ms	10948 KB	Output is correct
13	Correct	131 ms	8952 KB	Output is correct
14	Incorrect	427 ms	8952 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2512 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	76 ms	7628 KB	Output is correct
10	Correct	49 ms	6660 KB	Output is correct
11	Correct	37 ms	5980 KB	Output is correct
12	Correct	29 ms	5880 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	5 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	194 ms	10936 KB	Output is correct
12	Correct	191 ms	10948 KB	Output is correct
13	Correct	131 ms	8952 KB	Output is correct
14	Incorrect	427 ms	8952 KB	Output isn't correct
15	Halted	0 ms	0 KB	-