Submission #526482

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526482	2022-02-15T01:26:21 Z	PurpleCrayon	Self Study (JOI22_ho_t2)	C++17	0 / 100	460 ms	5356 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 2e5+10, MOD = 1e9+7;
const ll INF = (long long)1e18+10;

void solve() {
    // a[i] := max(a[i], b[i])
    // binary search, take the minimum number of a's such that I'm satisfied

    int n; ll m; cin >> n >> m;
    vector<ll> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    for (int i = 0; i < n; i++) a[i] = max(a[i], b[i]);

    auto v = [&](ll x) -> bool {
        ll has = 0;
        for (int i = 0; i < n; i++) {
            ll need = (x + a[i] - 1) / a[i];
            if (need <= m) has += m - need;
            else has -= (x - a[i] * m + b[i] - 1) / b[i];
        }
        return has >= 0;
    };

    ll lo = 0, hi = INF, mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (v(mid)) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }
    cout << lo << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	4 ms	460 KB	Output is correct
11	Correct	219 ms	5132 KB	Output is correct
12	Correct	219 ms	5068 KB	Output is correct
13	Correct	240 ms	5356 KB	Output is correct
14	Incorrect	460 ms	5264 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	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	114 ms	2764 KB	Output is correct
10	Correct	76 ms	1996 KB	Output is correct
11	Correct	58 ms	1624 KB	Output is correct
12	Correct	49 ms	1388 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	208 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	9 ms	392 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	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	4 ms	460 KB	Output is correct
11	Correct	219 ms	5132 KB	Output is correct
12	Correct	219 ms	5068 KB	Output is correct
13	Correct	240 ms	5356 KB	Output is correct
14	Incorrect	460 ms	5264 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	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	114 ms	2764 KB	Output is correct
10	Correct	76 ms	1996 KB	Output is correct
11	Correct	58 ms	1624 KB	Output is correct
12	Correct	49 ms	1388 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	208 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	9 ms	392 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	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	4 ms	460 KB	Output is correct
11	Correct	219 ms	5132 KB	Output is correct
12	Correct	219 ms	5068 KB	Output is correct
13	Correct	240 ms	5356 KB	Output is correct
14	Incorrect	460 ms	5264 KB	Output isn't correct
15	Halted	0 ms	0 KB	-