답안 #538052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538052	2022-03-16T04:07:27 Z	ddy888	Self Study (JOI22_ho_t2)	C++17	10 / 100	77 ms	6860 KB

Main

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

int N, M;
int A[300010], B[300010];

int good(int x) {
    int cnt = 0;
    for (int i = 1; i <= N; ++i) {
        int co, st;
        if (A[i] >= B[i]) { 
            if (M * A[i] < x) {
                co = M;
                st = (x - (M * A[i]) + B[i] - 1) / B[i];
            } else {
                co = (x + A[i] - 1) / A[i];
                st = 0;
            }
        } else {
            st = (x + B[i] - 1) / B[i];
            co = 0;
        }
        if (st * B[i] + co * A[i] < x) return 0;
        cnt += co + st;
    }
    return cnt <= M * N;
}

signed main() {
    fast;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];
    if (M == 1) {
        int ans = 1e18;
        for (int i = 1; i <= N; ++i) ans = min(ans, max(A[i], B[i]));
        cout << ans;
        return 0;
    }
    int lo = 0, hi = 1e16;
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (good(mid)) lo = mid;
        else hi = mid;
    }
    cout << lo;
    return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	58 ms	5040 KB	Output is correct
12	Correct	59 ms	5060 KB	Output is correct
13	Correct	50 ms	5052 KB	Output is correct
14	Correct	53 ms	4964 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	30 ms	5204 KB	Output is correct
17	Correct	75 ms	6776 KB	Output is correct
18	Correct	58 ms	6860 KB	Output is correct

Subtask #2

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	30 ms	5204 KB	Output is correct
3	Correct	75 ms	6776 KB	Output is correct
4	Correct	58 ms	6860 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	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	77 ms	2804 KB	Output is correct
14	Correct	49 ms	1964 KB	Output is correct
15	Correct	37 ms	1504 KB	Output is correct
16	Correct	29 ms	1236 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Incorrect	5 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	58 ms	5040 KB	Output is correct
12	Correct	59 ms	5060 KB	Output is correct
13	Correct	50 ms	5052 KB	Output is correct
14	Correct	53 ms	4964 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	77 ms	2804 KB	Output is correct
24	Correct	49 ms	1964 KB	Output is correct
25	Correct	37 ms	1504 KB	Output is correct
26	Correct	29 ms	1236 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Incorrect	5 ms	340 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	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	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	77 ms	2804 KB	Output is correct
10	Correct	49 ms	1964 KB	Output is correct
11	Correct	37 ms	1504 KB	Output is correct
12	Correct	29 ms	1236 KB	Output is correct
13	Correct	1 ms	340 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	212 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Incorrect	5 ms	340 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	58 ms	5040 KB	Output is correct
12	Correct	59 ms	5060 KB	Output is correct
13	Correct	50 ms	5052 KB	Output is correct
14	Correct	53 ms	4964 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	77 ms	2804 KB	Output is correct
24	Correct	49 ms	1964 KB	Output is correct
25	Correct	37 ms	1504 KB	Output is correct
26	Correct	29 ms	1236 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Incorrect	5 ms	340 KB	Output isn't correct
33	Halted	0 ms	0 KB	-