# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
527313 |
2022-02-17T05:58:10 Z |
ac2hu |
Self Study (JOI22_ho_t2) |
C++14 |
|
393 ms |
9672 KB |
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
// O(N log(MAXN)) = O(60N)
const int N = 3e5 + 10;
int a[N],b[N];
int n,m;
bool check(int mid,bool debug){
if(debug)
cout << mid << "---> \n";
int c = 0;
for(int i = 0;i<n;i++){
// We have to reach a minimum of mid
if(a[i] > b[i]){
int mx = (mid + a[i] - 1)/a[i];
mx = min(mx,m);
if(mid < mx*a[i]){
c += mx;
continue;
}
int temp = mid - mx*a[i];
int temp123 = max((temp + b[i] - 1)/b[i],0ull);
c += mx + temp123;
if(debug)
cout << mx << " " << temp123 << "\n";
}
else{
int mx = (mid + b[i] - 1)/b[i];
c += mx;
if(debug)
cout << mx << "\n";
}
}
if(c <= n*m)
return true;
else
return false;
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> m;
for(int i =0;i<n;i++)cin >> a[i];
for(int i = 0;i<n;i++)cin >> b[i];
int l = 0,r = 2e18;
while(l < r){
int mid = (l + r + 1)/2;
if(check(mid,false))
l = mid;
else
r = mid - 1;
}
// check(r,true);
assert(check(r,false));
while(check(r + 1,false))
r++;
cout << r << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 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 |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
4 ms |
416 KB |
Output is correct |
11 |
Correct |
207 ms |
9540 KB |
Output is correct |
12 |
Correct |
213 ms |
9392 KB |
Output is correct |
13 |
Correct |
159 ms |
6536 KB |
Output is correct |
14 |
Correct |
299 ms |
8656 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
201 ms |
5316 KB |
Output is correct |
17 |
Correct |
182 ms |
5752 KB |
Output is correct |
18 |
Correct |
166 ms |
6212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
201 ms |
5316 KB |
Output is correct |
3 |
Correct |
182 ms |
5752 KB |
Output is correct |
4 |
Correct |
166 ms |
6212 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 |
320 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
87 ms |
4700 KB |
Output is correct |
14 |
Correct |
59 ms |
2696 KB |
Output is correct |
15 |
Correct |
43 ms |
2124 KB |
Output is correct |
16 |
Correct |
36 ms |
1780 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
4 ms |
368 KB |
Output is correct |
23 |
Correct |
4 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 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 |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
4 ms |
416 KB |
Output is correct |
11 |
Correct |
207 ms |
9540 KB |
Output is correct |
12 |
Correct |
213 ms |
9392 KB |
Output is correct |
13 |
Correct |
159 ms |
6536 KB |
Output is correct |
14 |
Correct |
299 ms |
8656 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
87 ms |
4700 KB |
Output is correct |
24 |
Correct |
59 ms |
2696 KB |
Output is correct |
25 |
Correct |
43 ms |
2124 KB |
Output is correct |
26 |
Correct |
36 ms |
1780 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
320 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
332 KB |
Output is correct |
32 |
Correct |
4 ms |
368 KB |
Output is correct |
33 |
Correct |
4 ms |
452 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
201 ms |
5316 KB |
Output is correct |
36 |
Correct |
182 ms |
5752 KB |
Output is correct |
37 |
Correct |
166 ms |
6212 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
296 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
0 ms |
204 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
0 ms |
204 KB |
Output is correct |
44 |
Correct |
0 ms |
204 KB |
Output is correct |
45 |
Correct |
4 ms |
436 KB |
Output is correct |
46 |
Correct |
7 ms |
568 KB |
Output is correct |
47 |
Correct |
1 ms |
332 KB |
Output is correct |
48 |
Correct |
37 ms |
1652 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |
50 |
Correct |
1 ms |
204 KB |
Output is correct |
51 |
Correct |
4 ms |
336 KB |
Output is correct |
52 |
Correct |
0 ms |
204 KB |
Output is correct |
53 |
Correct |
1 ms |
204 KB |
Output is correct |
54 |
Correct |
1 ms |
316 KB |
Output is correct |
55 |
Correct |
106 ms |
4320 KB |
Output is correct |
56 |
Correct |
56 ms |
2440 KB |
Output is correct |
57 |
Correct |
102 ms |
2512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
87 ms |
4700 KB |
Output is correct |
10 |
Correct |
59 ms |
2696 KB |
Output is correct |
11 |
Correct |
43 ms |
2124 KB |
Output is correct |
12 |
Correct |
36 ms |
1780 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
320 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
4 ms |
368 KB |
Output is correct |
19 |
Correct |
4 ms |
452 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
201 ms |
5316 KB |
Output is correct |
22 |
Correct |
182 ms |
5752 KB |
Output is correct |
23 |
Correct |
166 ms |
6212 KB |
Output is correct |
24 |
Correct |
36 ms |
1360 KB |
Output is correct |
25 |
Correct |
90 ms |
3268 KB |
Output is correct |
26 |
Correct |
19 ms |
964 KB |
Output is correct |
27 |
Correct |
167 ms |
6752 KB |
Output is correct |
28 |
Correct |
169 ms |
6748 KB |
Output is correct |
29 |
Correct |
171 ms |
6668 KB |
Output is correct |
30 |
Correct |
178 ms |
6784 KB |
Output is correct |
31 |
Correct |
221 ms |
7948 KB |
Output is correct |
32 |
Correct |
230 ms |
5568 KB |
Output is correct |
33 |
Correct |
244 ms |
6724 KB |
Output is correct |
34 |
Correct |
229 ms |
4936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 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 |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
4 ms |
416 KB |
Output is correct |
11 |
Correct |
207 ms |
9540 KB |
Output is correct |
12 |
Correct |
213 ms |
9392 KB |
Output is correct |
13 |
Correct |
159 ms |
6536 KB |
Output is correct |
14 |
Correct |
299 ms |
8656 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
320 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
87 ms |
4700 KB |
Output is correct |
24 |
Correct |
59 ms |
2696 KB |
Output is correct |
25 |
Correct |
43 ms |
2124 KB |
Output is correct |
26 |
Correct |
36 ms |
1780 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
320 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
332 KB |
Output is correct |
32 |
Correct |
4 ms |
368 KB |
Output is correct |
33 |
Correct |
4 ms |
452 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
296 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
4 ms |
436 KB |
Output is correct |
42 |
Correct |
7 ms |
568 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
37 ms |
1652 KB |
Output is correct |
45 |
Correct |
1 ms |
204 KB |
Output is correct |
46 |
Correct |
1 ms |
204 KB |
Output is correct |
47 |
Correct |
4 ms |
336 KB |
Output is correct |
48 |
Correct |
0 ms |
204 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |
50 |
Correct |
1 ms |
316 KB |
Output is correct |
51 |
Correct |
106 ms |
4320 KB |
Output is correct |
52 |
Correct |
56 ms |
2440 KB |
Output is correct |
53 |
Correct |
102 ms |
2512 KB |
Output is correct |
54 |
Correct |
36 ms |
1360 KB |
Output is correct |
55 |
Correct |
90 ms |
3268 KB |
Output is correct |
56 |
Correct |
19 ms |
964 KB |
Output is correct |
57 |
Correct |
167 ms |
6752 KB |
Output is correct |
58 |
Correct |
169 ms |
6748 KB |
Output is correct |
59 |
Correct |
171 ms |
6668 KB |
Output is correct |
60 |
Correct |
178 ms |
6784 KB |
Output is correct |
61 |
Correct |
221 ms |
7948 KB |
Output is correct |
62 |
Correct |
230 ms |
5568 KB |
Output is correct |
63 |
Correct |
244 ms |
6724 KB |
Output is correct |
64 |
Correct |
229 ms |
4936 KB |
Output is correct |
65 |
Correct |
0 ms |
204 KB |
Output is correct |
66 |
Correct |
201 ms |
5316 KB |
Output is correct |
67 |
Correct |
182 ms |
5752 KB |
Output is correct |
68 |
Correct |
166 ms |
6212 KB |
Output is correct |
69 |
Correct |
27 ms |
956 KB |
Output is correct |
70 |
Correct |
7 ms |
332 KB |
Output is correct |
71 |
Correct |
1 ms |
204 KB |
Output is correct |
72 |
Correct |
37 ms |
1236 KB |
Output is correct |
73 |
Correct |
9 ms |
532 KB |
Output is correct |
74 |
Correct |
1 ms |
340 KB |
Output is correct |
75 |
Correct |
214 ms |
7012 KB |
Output is correct |
76 |
Correct |
211 ms |
6776 KB |
Output is correct |
77 |
Correct |
212 ms |
6232 KB |
Output is correct |
78 |
Correct |
236 ms |
5268 KB |
Output is correct |
79 |
Correct |
240 ms |
6732 KB |
Output is correct |
80 |
Correct |
247 ms |
9672 KB |
Output is correct |
81 |
Correct |
224 ms |
6448 KB |
Output is correct |
82 |
Correct |
393 ms |
6824 KB |
Output is correct |