답안 #526481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526481	2022-02-15T01:21:53 Z	PurpleCrayon	Self Study (JOI22_ho_t2)	C++17	0 / 100	464 ms	9444 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 = 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	212 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	1 ms	216 KB	Output is correct
10	Correct	4 ms	404 KB	Output is correct
11	Correct	233 ms	9444 KB	Output is correct
12	Correct	231 ms	9268 KB	Output is correct
13	Correct	239 ms	6724 KB	Output is correct
14	Incorrect	464 ms	8672 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 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	1 ms	212 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	117 ms	4680 KB	Output is correct
10	Correct	78 ms	2636 KB	Output is correct
11	Correct	57 ms	2156 KB	Output is correct
12	Correct	49 ms	1856 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	224 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	212 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	1 ms	216 KB	Output is correct
10	Correct	4 ms	404 KB	Output is correct
11	Correct	233 ms	9444 KB	Output is correct
12	Correct	231 ms	9268 KB	Output is correct
13	Correct	239 ms	6724 KB	Output is correct
14	Incorrect	464 ms	8672 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 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	1 ms	212 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	117 ms	4680 KB	Output is correct
10	Correct	78 ms	2636 KB	Output is correct
11	Correct	57 ms	2156 KB	Output is correct
12	Correct	49 ms	1856 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	224 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	212 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	1 ms	216 KB	Output is correct
10	Correct	4 ms	404 KB	Output is correct
11	Correct	233 ms	9444 KB	Output is correct
12	Correct	231 ms	9268 KB	Output is correct
13	Correct	239 ms	6724 KB	Output is correct
14	Incorrect	464 ms	8672 KB	Output isn't correct
15	Halted	0 ms	0 KB	-