Submission #879933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
879933	2023-11-28T11:07:02 Z	frostray8653	Self Study (JOI22_ho_t2)	C++17	0 / 100	432 ms	5152 KB

Main

#include <bits/stdc++.h>
#define int long long
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
using pii = pair<int, int>;
const int N = 300005;
const int INF = 2e18;
int n, m;
int a[N], b[N];

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

signed main() {
    IO;
    cin >> n >> m;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];

    int l = 0, r = INF;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << "\n";

    return 0;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 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	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	182 ms	5152 KB	Output is correct
12	Correct	183 ms	4944 KB	Output is correct
13	Correct	132 ms	4952 KB	Output is correct
14	Incorrect	432 ms	5132 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 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	106 ms	4700 KB	Output is correct
10	Correct	70 ms	4724 KB	Output is correct
11	Correct	53 ms	4700 KB	Output is correct
12	Correct	43 ms	4696 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2504 KB	Output is correct
18	Incorrect	9 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	0 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	0 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	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	182 ms	5152 KB	Output is correct
12	Correct	183 ms	4944 KB	Output is correct
13	Correct	132 ms	4952 KB	Output is correct
14	Incorrect	432 ms	5132 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 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	106 ms	4700 KB	Output is correct
10	Correct	70 ms	4724 KB	Output is correct
11	Correct	53 ms	4700 KB	Output is correct
12	Correct	43 ms	4696 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2504 KB	Output is correct
18	Incorrect	9 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	0 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	0 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	2396 KB	Output is correct
10	Correct	3 ms	2396 KB	Output is correct
11	Correct	182 ms	5152 KB	Output is correct
12	Correct	183 ms	4944 KB	Output is correct
13	Correct	132 ms	4952 KB	Output is correct
14	Incorrect	432 ms	5132 KB	Output isn't correct
15	Halted	0 ms	0 KB	-