Submission #593546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593546	2022-07-11T11:24:57 Z	oleh1421	Self Study (JOI22_ho_t2)	C++17	0 / 100	306 ms	5120 KB

Main

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=600010;
const int Lg=16;
ll a[N],b[N];
int n,m;
bool ok(ll D){
    ll sum=0ll;
    for (int i=1;i<=n;i++){
        if (a[i]*m>=D){
            sum+=m-(D+a[i]-1)/a[i];
        } else {
            sum-=(D-a[i]*m+b[i]-1)/b[i];
        }
    }
    return (sum>=0);
}
void solve(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) cin>>b[i];
    for (int i=1;i<=n;i++) a[i]=max(a[i],b[i]);
    ll ans=0ll;
    for (ll i=60;i>=0;i--){
        if (ok(ans+(1ll<<i))) ans+=(1ll<<i);
    }
    cout<<ans<<endl;

}
int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

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	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	159 ms	5020 KB	Output is correct
12	Correct	164 ms	5020 KB	Output is correct
13	Correct	173 ms	5024 KB	Output is correct
14	Incorrect	306 ms	5120 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	340 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	340 KB	Output is correct
9	Correct	84 ms	2672 KB	Output is correct
10	Correct	60 ms	1884 KB	Output is correct
11	Correct	44 ms	1500 KB	Output is correct
12	Correct	33 ms	1176 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	5 ms	364 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	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	159 ms	5020 KB	Output is correct
12	Correct	164 ms	5020 KB	Output is correct
13	Correct	173 ms	5024 KB	Output is correct
14	Incorrect	306 ms	5120 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	340 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	340 KB	Output is correct
9	Correct	84 ms	2672 KB	Output is correct
10	Correct	60 ms	1884 KB	Output is correct
11	Correct	44 ms	1500 KB	Output is correct
12	Correct	33 ms	1176 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 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	5 ms	364 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	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	159 ms	5020 KB	Output is correct
12	Correct	164 ms	5020 KB	Output is correct
13	Correct	173 ms	5024 KB	Output is correct
14	Incorrect	306 ms	5120 KB	Output isn't correct
15	Halted	0 ms	0 KB	-