oj.uz

Submission #798348

# Submission time Handle Problem Language Result Execution time Memory
798348 2023-07-30T15:48:43 Z n3rm1n Self Study (JOI22_ho_t2) C++17
0 / 100
 403 ms 9724 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 = 1e17, 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 6 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 7 ms 5076 KB Output is correct
8 Correct 7 ms 5024 KB Output is correct
9 Correct 6 ms 4948 KB Output is correct
10 Correct 9 ms 5112 KB Output is correct
11 Correct 176 ms 9696 KB Output is correct
12 Correct 174 ms 9640 KB Output is correct
13 Correct 131 ms 9640 KB Output is correct
14 Incorrect 403 ms 9724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5024 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 7 ms 5028 KB Output is correct
8 Correct 6 ms 5028 KB Output is correct
9 Correct 74 ms 7252 KB Output is correct
10 Correct 52 ms 6484 KB Output is correct
11 Correct 41 ms 6180 KB Output is correct
12 Correct 35 ms 5972 KB Output is correct
13 Correct 6 ms 5044 KB Output is correct
14 Correct 6 ms 4948 KB Output is correct
15 Correct 7 ms 5024 KB Output is correct
16 Correct 6 ms 5032 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Incorrect 10 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 6 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 7 ms 5076 KB Output is correct
8 Correct 7 ms 5024 KB Output is correct
9 Correct 6 ms 4948 KB Output is correct
10 Correct 9 ms 5112 KB Output is correct
11 Correct 176 ms 9696 KB Output is correct
12 Correct 174 ms 9640 KB Output is correct
13 Correct 131 ms 9640 KB Output is correct
14 Incorrect 403 ms 9724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5024 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 7 ms 5028 KB Output is correct
8 Correct 6 ms 5028 KB Output is correct
9 Correct 74 ms 7252 KB Output is correct
10 Correct 52 ms 6484 KB Output is correct
11 Correct 41 ms 6180 KB Output is correct
12 Correct 35 ms 5972 KB Output is correct
13 Correct 6 ms 5044 KB Output is correct
14 Correct 6 ms 4948 KB Output is correct
15 Correct 7 ms 5024 KB Output is correct
16 Correct 6 ms 5032 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Incorrect 10 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 6 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 7 ms 5076 KB Output is correct
8 Correct 7 ms 5024 KB Output is correct
9 Correct 6 ms 4948 KB Output is correct
10 Correct 9 ms 5112 KB Output is correct
11 Correct 176 ms 9696 KB Output is correct
12 Correct 174 ms 9640 KB Output is correct
13 Correct 131 ms 9640 KB Output is correct
14 Incorrect 403 ms 9724 KB Output isn't correct
15 Halted 0 ms 0 KB -