Submission #538666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538666	2022-03-17T12:07:30 Z	faruk	Self Study (JOI22_ho_t2)	C++17	0 / 100	1000 ms	2664 KB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double

using namespace std;

vector<ll> a;
vector<ll> b;
int n; ll m;
bool binary(ll x) {
    ll possible = 0;
    for (int i = 0; i < n ; i++) {
        ll val = a[i] * m;
        if (val < x)
            continue;
        ll diff = val - x;
        possible += diff / a[i];
    }

    for (int i = 0; i < n; i++) {
        ll val = a[i] * m;
        if (val >= x)
            continue;
        ll dif = x - val;
        ll needed = dif / b[i];
        if (dif % b[i])
        possible -= ceil((ld)dif / (ld)b[i]);
    }
    return possible < 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    a.resize(n);
    b.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        a[i] = max(a[i], b[i]);
    }

    ll l = 0, r = 6e18;
    while (l < r) {
        ll mid = (l + r) / 2;
        if (binary(mid))
            r = mid;
        else
            l = mid + 1;
    }

    cout << l - 1<< "\n";
}

Compilation message

Main.cpp: In function 'bool binary(long long int)':
Main.cpp:26:12: warning: unused variable 'needed' [-Wunused-variable]
   26 |         ll needed = dif / b[i];
      |            ^~~~~~

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	124 ms	2664 KB	Output is correct
10	Correct	90 ms	1876 KB	Output is correct
11	Correct	56 ms	1492 KB	Output is correct
12	Correct	44 ms	1236 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Execution timed out	1088 ms	212 KB	Time limit exceeded
17	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	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	124 ms	2664 KB	Output is correct
10	Correct	90 ms	1876 KB	Output is correct
11	Correct	56 ms	1492 KB	Output is correct
12	Correct	44 ms	1236 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Execution timed out	1088 ms	212 KB	Time limit exceeded
17	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	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	Halted	0 ms	0 KB	-