oj.uz

Submission #828178

# Submission time Handle Problem Language Result Execution time Memory
828178 2023-08-17T06:21:30 Z RaresFelix Self Study (JOI22_ho_t2) C++17
0 / 100
 516 ms 4980 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MN = 300001;
const ll INF = 1e18 + 71;

ll n, m, A[MN], B[MN];
ll mini = INF;

bool ok(ll val, int dbg) {
    if(!val) return 1;
    ll nr_sar = 0;
    for(int i = 1; i <= n; ++i) {
        if((val - 1) / A[i] + 1 <= m) {
            nr_sar += m - ((val - 1) / A[i] + 1);
            assert((m - ((val - 1) / A[i] + 1)) >= 0);
        } else {
            nr_sar -= (val - m * A[i] - 1) / B[i] + 1;
            assert(((val - m * A[i] - 1) / B[i] + 1) >= 0);
        }
    }
    return (nr_sar >= 0);
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> A[i];
    for(int i = 1; i <= n; ++i) {
        cin >> B[i];
        if(A[i] < B[i]) A[i] = B[i];
    }
    for(int i = 1; i <= n; ++i) mini = min(A[i], mini);
    ll st = 0, dr = INF, mij;
    while(st < dr) {
        mij = st + (dr - st + 1) / 2;
        if(ok(mij, 0)) {
            st = mij;
        }  else dr = mij - 1;
    }
    if(m == 1) {
        ok(st, 1);
        cout << st << "\n";
    } else 
        cout << st << "\n";
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 320 ms 4904 KB Output is correct
12 Correct 336 ms 4884 KB Output is correct
13 Correct 293 ms 4916 KB Output is correct
14 Incorrect 516 ms 4980 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 162 ms 2636 KB Output is correct
10 Correct 111 ms 1784 KB Output is correct
11 Correct 80 ms 1372 KB Output is correct
12 Correct 65 ms 1232 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
18 Incorrect 9 ms 384 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 212 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 320 ms 4904 KB Output is correct
12 Correct 336 ms 4884 KB Output is correct
13 Correct 293 ms 4916 KB Output is correct
14 Incorrect 516 ms 4980 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 162 ms 2636 KB Output is correct
10 Correct 111 ms 1784 KB Output is correct
11 Correct 80 ms 1372 KB Output is correct
12 Correct 65 ms 1232 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
18 Incorrect 9 ms 384 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 212 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 320 ms 4904 KB Output is correct
12 Correct 336 ms 4884 KB Output is correct
13 Correct 293 ms 4916 KB Output is correct
14 Incorrect 516 ms 4980 KB Output isn't correct
15 Halted 0 ms 0 KB -