Submission #921488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921488	2024-02-04T02:42:47 Z	LiuBruh	Self Study (JOI22_ho_t2)	C++17	0 / 100	275 ms	7488 KB

Main

#include <bits/stdc++.h>

#define int long long
#define sz(v) (int)v.size()
using namespace std;

const int maxn = (int)3e5 + 5;
const int INF = (int)1e18 + 5;

int n, m;
int a[maxn], b[maxn];

bool check(int x) {
    int rem = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] * m >= x) {
            rem += m - ((x + a[i] - 1) / a[i]);
        } else {
            rem -= (x - a[i] * m + b[i] - 1) / b[i];
        }
    }
    return rem >= 0;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) a[i] = max(a[i], b[i]);

    int l = 1, r = (int)2e18, mid;
    while (l < r) {
        mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

Subtask #1

0 / 10.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	0 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	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	149 ms	5072 KB	Output is correct
12	Correct	172 ms	5132 KB	Output is correct
13	Correct	133 ms	5132 KB	Output is correct
14	Incorrect	275 ms	5216 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	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2512 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	2448 KB	Output is correct
9	Correct	76 ms	7488 KB	Output is correct
10	Correct	50 ms	6492 KB	Output is correct
11	Correct	38 ms	5976 KB	Output is correct
12	Correct	30 ms	5724 KB	Output is correct
13	Correct	1 ms	2392 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	2392 KB	Output is correct
17	Correct	1 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 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	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	149 ms	5072 KB	Output is correct
12	Correct	172 ms	5132 KB	Output is correct
13	Correct	133 ms	5132 KB	Output is correct
14	Incorrect	275 ms	5216 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	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2512 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	2448 KB	Output is correct
9	Correct	76 ms	7488 KB	Output is correct
10	Correct	50 ms	6492 KB	Output is correct
11	Correct	38 ms	5976 KB	Output is correct
12	Correct	30 ms	5724 KB	Output is correct
13	Correct	1 ms	2392 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	2392 KB	Output is correct
17	Correct	1 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 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	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	149 ms	5072 KB	Output is correct
12	Correct	172 ms	5132 KB	Output is correct
13	Correct	133 ms	5132 KB	Output is correct
14	Incorrect	275 ms	5216 KB	Output isn't correct
15	Halted	0 ms	0 KB	-