oj.uz

Submission #798345

# Submission time Handle Problem Language Result Execution time Memory
798345 2023-07-30T15:46:40 Z n3rm1n Self Study (JOI22_ho_t2) C++17
0 / 100
 445 ms 15512 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long  MAXN = 3e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long  n, m;
long long  a[MAXN], b[MAXN];
void read()
{
    cin >> n >> m;
    for (long long  i = 1; i <= n; ++ i)
        cin >> a[i];
    for (long long  i = 1; i <= n; ++ i)
        cin >> b[i];
}
long long  useda[MAXN], needb[MAXN];
bool check(long long  x)
{
    memset(useda, 0, sizeof(useda));
    memset(needb, 0, sizeof(needb));
    long long  suma = 0, sumb = 0;
    for (long long  i = 1; i <= n; ++ i)
    {
        if(a[i] > b[i])
        {
            long long  times = x / a[i];
            if(x % a[i] != 0)times ++;
            times = min(m, times);
            useda[i] = times;
            long long  ost = max(1LL * 0, x - times * a[i]);
            needb[i] = ost / b[i];
            if(ost % b[i] != 0)needb[i] ++;
        }
        else
        {
            needb[i] = x / b[i];
            if(x % b[i] != 0)needb[i] ++;
        }
        suma += useda[i];
        sumb += needb[i];
    }

    return (sumb <= n * m - suma);
}
void solve()
{
    long long  l = 0, r = 1e18, mid, ans = 0;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 7 ms 4932 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 7 ms 5032 KB Output is correct
7 Correct 7 ms 4948 KB Output is correct
8 Correct 8 ms 5032 KB Output is correct
9 Correct 7 ms 5032 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 193 ms 15508 KB Output is correct
12 Correct 188 ms 15512 KB Output is correct
13 Correct 152 ms 13456 KB Output is correct
14 Incorrect 445 ms 13520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5000 KB Output is correct
2 Correct 7 ms 4936 KB Output is correct
3 Correct 7 ms 5040 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 5036 KB Output is correct
6 Correct 7 ms 4948 KB Output is correct
7 Correct 7 ms 4940 KB Output is correct
8 Correct 7 ms 5036 KB Output is correct
9 Correct 79 ms 10272 KB Output is correct
10 Correct 56 ms 8412 KB Output is correct
11 Correct 43 ms 7544 KB Output is correct
12 Correct 36 ms 7056 KB Output is correct
13 Correct 7 ms 4948 KB Output is correct
14 Correct 8 ms 4948 KB Output is correct
15 Correct 7 ms 4948 KB Output is correct
16 Correct 7 ms 4948 KB Output is correct
17 Correct 7 ms 4948 KB Output is correct
18 Incorrect 11 ms 5076 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 7 ms 4932 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 7 ms 5032 KB Output is correct
7 Correct 7 ms 4948 KB Output is correct
8 Correct 8 ms 5032 KB Output is correct
9 Correct 7 ms 5032 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 193 ms 15508 KB Output is correct
12 Correct 188 ms 15512 KB Output is correct
13 Correct 152 ms 13456 KB Output is correct
14 Incorrect 445 ms 13520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5000 KB Output is correct
2 Correct 7 ms 4936 KB Output is correct
3 Correct 7 ms 5040 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 5036 KB Output is correct
6 Correct 7 ms 4948 KB Output is correct
7 Correct 7 ms 4940 KB Output is correct
8 Correct 7 ms 5036 KB Output is correct
9 Correct 79 ms 10272 KB Output is correct
10 Correct 56 ms 8412 KB Output is correct
11 Correct 43 ms 7544 KB Output is correct
12 Correct 36 ms 7056 KB Output is correct
13 Correct 7 ms 4948 KB Output is correct
14 Correct 8 ms 4948 KB Output is correct
15 Correct 7 ms 4948 KB Output is correct
16 Correct 7 ms 4948 KB Output is correct
17 Correct 7 ms 4948 KB Output is correct
18 Incorrect 11 ms 5076 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 7 ms 4932 KB Output is correct
4 Correct 7 ms 5040 KB Output is correct
5 Correct 7 ms 4948 KB Output is correct
6 Correct 7 ms 5032 KB Output is correct
7 Correct 7 ms 4948 KB Output is correct
8 Correct 8 ms 5032 KB Output is correct
9 Correct 7 ms 5032 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 193 ms 15508 KB Output is correct
12 Correct 188 ms 15512 KB Output is correct
13 Correct 152 ms 13456 KB Output is correct
14 Incorrect 445 ms 13520 KB Output isn't correct
15 Halted 0 ms 0 KB -