oj.uz

Submission #855541

# Submission time Handle Problem Language Result Execution time Memory
855541 2023-10-01T11:58:10 Z ancuber1031 Self Study (JOI22_ho_t2) C++14
0 / 100
 998 ms 10932 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int __int128
#define pii pair<int,int>
#define p_q priority_queue
#define endl '\n'
#define pb push_back

long long n, m;
vector<long long> a, b;

bool check(int mid) {
    int rem = n*m;
    for (int i = 0; i < n; ++i) {
        if (a[i] > b[i]) {
            if (a[i]*m >= mid) {
                rem -= mid/a[i]+(mid%a[i] > 0);
            } else {
                int cur = mid-a[i]*m;
                rem -= m;
                rem -= cur/b[i]+(cur%b[i] > 0);
            }
        } else {
            if (mid%b[i]) rem -= (mid/b[i]+1);
            else rem -= mid/b[i];
            //rem -= mid/b[i]+(mid%b[i] > 0);
        }
    }
    return rem >= 0;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    a.resize(n), b.resize(n);
    for (auto& i : a) cin>>i;
    for (auto& i : b) cin>>i;
    
    int l = 0, r = 4e36;
    while(r-l > 1) {
        int mid = r+(l-r)/2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    long long ans = l;
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 547 ms 10932 KB Output is correct
12 Correct 521 ms 10836 KB Output is correct
13 Correct 416 ms 8720 KB Output is correct
14 Incorrect 998 ms 8788 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 217 ms 5696 KB Output is correct
10 Correct 144 ms 3948 KB Output is correct
11 Correct 108 ms 3080 KB Output is correct
12 Correct 88 ms 2392 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 16 ms 548 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 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 547 ms 10932 KB Output is correct
12 Correct 521 ms 10836 KB Output is correct
13 Correct 416 ms 8720 KB Output is correct
14 Incorrect 998 ms 8788 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 217 ms 5696 KB Output is correct
10 Correct 144 ms 3948 KB Output is correct
11 Correct 108 ms 3080 KB Output is correct
12 Correct 88 ms 2392 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 16 ms 548 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 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 547 ms 10932 KB Output is correct
12 Correct 521 ms 10836 KB Output is correct
13 Correct 416 ms 8720 KB Output is correct
14 Incorrect 998 ms 8788 KB Output isn't correct
15 Halted 0 ms 0 KB -