Submission #702928

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
702928	2023-02-25T10:21:42 Z	stevancv	Self Study (JOI22_ho_t2)	C++14	0 / 100	600 ms	10756 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);
    ll n, m;
    cin >> n >> m;
    vector<array<ll, 2>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i][0];
    for (int i = 0; i < n; i++) cin >> a[i][1];
    auto Can = [&] (ll x) {
        ll kol = 0;
        for (int i = 0; i < n; i++) kol += C(x, a[i][1]);
        if (kol <= n * m) return 1;
        for (int i = 0; i < n; i++) {
            ll u = min(C(x, a[i][0]), m);
            ll s = C(x - u * a[i][0], a[i][1]);
            if (u + s < C(x, a[i][1])) kol += u + s - C(x, a[i][1]);
        }
        if (kol <= n * m) return 1;
        return 0;
    };
    ll l = 0, r = 1e15, 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:38:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         ll mid = l + r >> 1;
      |                  ~~^~~

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	354 ms	10752 KB	Output is correct
12	Correct	357 ms	10756 KB	Output is correct
13	Correct	346 ms	8708 KB	Output is correct
14	Incorrect	600 ms	8704 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 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	212 KB	Output is correct
9	Correct	157 ms	5468 KB	Output is correct
10	Correct	100 ms	3796 KB	Output is correct
11	Correct	81 ms	2884 KB	Output is correct
12	Correct	65 ms	2388 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	320 KB	Output is correct
17	Correct	1 ms	312 KB	Output is correct
18	Correct	9 ms	408 KB	Output is correct
19	Correct	7 ms	456 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Incorrect	534 ms	6092 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	354 ms	10752 KB	Output is correct
12	Correct	357 ms	10756 KB	Output is correct
13	Correct	346 ms	8708 KB	Output is correct
14	Incorrect	600 ms	8704 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 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	212 KB	Output is correct
9	Correct	157 ms	5468 KB	Output is correct
10	Correct	100 ms	3796 KB	Output is correct
11	Correct	81 ms	2884 KB	Output is correct
12	Correct	65 ms	2388 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	320 KB	Output is correct
17	Correct	1 ms	312 KB	Output is correct
18	Correct	9 ms	408 KB	Output is correct
19	Correct	7 ms	456 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Incorrect	534 ms	6092 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	6 ms	468 KB	Output is correct
11	Correct	354 ms	10752 KB	Output is correct
12	Correct	357 ms	10756 KB	Output is correct
13	Correct	346 ms	8708 KB	Output is correct
14	Incorrect	600 ms	8704 KB	Output isn't correct
15	Halted	0 ms	0 KB	-