Submission #941211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941211	2024-03-08T09:38:30 Z	peterandvoi	Self Study (JOI22_ho_t2)	C++17	0 / 100	274 ms	8828 KB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = (int) 3e5 + 5;

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

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    long long l = 1, r = 1e18, res = 0;
    while (l <= r) {
        long long mid = l + r >> 1;
        if (check(mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << res;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:48:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         long long mid = l + r >> 1;
      |                         ~~^~~

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 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	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2508 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	156 ms	8580 KB	Output is correct
12	Correct	150 ms	8828 KB	Output is correct
13	Correct	137 ms	6480 KB	Output is correct
14	Incorrect	274 ms	6592 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	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 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	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	74 ms	5568 KB	Output is correct
10	Correct	49 ms	4444 KB	Output is correct
11	Correct	37 ms	3932 KB	Output is correct
12	Correct	30 ms	3676 KB	Output is correct
13	Correct	1 ms	2648 KB	Output is correct
14	Correct	1 ms	2508 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 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	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	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2508 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	156 ms	8580 KB	Output is correct
12	Correct	150 ms	8828 KB	Output is correct
13	Correct	137 ms	6480 KB	Output is correct
14	Incorrect	274 ms	6592 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	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 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	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	74 ms	5568 KB	Output is correct
10	Correct	49 ms	4444 KB	Output is correct
11	Correct	37 ms	3932 KB	Output is correct
12	Correct	30 ms	3676 KB	Output is correct
13	Correct	1 ms	2648 KB	Output is correct
14	Correct	1 ms	2508 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 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	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	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2508 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	156 ms	8580 KB	Output is correct
12	Correct	150 ms	8828 KB	Output is correct
13	Correct	137 ms	6480 KB	Output is correct
14	Incorrect	274 ms	6592 KB	Output isn't correct
15	Halted	0 ms	0 KB	-