Submission #702969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
702969	2023-02-25T11:40:51 Z	stevancv	Self Study (JOI22_ho_t2)	C++14	0 / 100	724 ms	5144 KB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int inf = 2e9;
ll C(ll a, ll b) {
    if (a <= 0) return 0;
    return (a + b - 1) / b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    auto Can = [&] (ll x) {
        ll kol = 0;
        for (int i = 0; i < n; i++) {
            kol += C(x, b[i]);
            ll u = min(C(x, a[i]), m);
            ll s = C(x - u * a[i], b[i]);
            if (u + s < C(x, b[i])) kol += u + s - C(x, b[i]);
        }
        return kol <= n * m;
    };
    ll l = 1, r = 1e18, ans = l;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (Can(mid)) {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    cout << ans << en;
    return 0;
}

Compilation message

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

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	339 ms	5132 KB	Output is correct
12	Correct	332 ms	5136 KB	Output is correct
13	Correct	437 ms	5132 KB	Output is correct
14	Incorrect	724 ms	5144 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	175 ms	2708 KB	Output is correct
10	Correct	111 ms	2092 KB	Output is correct
11	Correct	83 ms	1624 KB	Output is correct
12	Correct	70 ms	1364 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	316 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	13 ms	416 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	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	339 ms	5132 KB	Output is correct
12	Correct	332 ms	5136 KB	Output is correct
13	Correct	437 ms	5132 KB	Output is correct
14	Incorrect	724 ms	5144 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	175 ms	2708 KB	Output is correct
10	Correct	111 ms	2092 KB	Output is correct
11	Correct	83 ms	1624 KB	Output is correct
12	Correct	70 ms	1364 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	316 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Incorrect	13 ms	416 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	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	339 ms	5132 KB	Output is correct
12	Correct	332 ms	5136 KB	Output is correct
13	Correct	437 ms	5132 KB	Output is correct
14	Incorrect	724 ms	5144 KB	Output isn't correct
15	Halted	0 ms	0 KB	-