This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl
using namespace std;
const long long oo = 1e18;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
freopen ( "sum.in", "r", stdin )
*/
int n, m, a[ 300001 ], b[ 300001 ];
bool ok( int x ) {
__int128 sum = 0;
for ( int i = 1; i <= n; i ++ ) {
num = x / a[ i ];
if ( x % a[ i ] ) {
num ++;
}
if ( num <= m )
sum += m - num;
else {
pos = ( num - m - 1 ) * a[ i ];
if ( x % a[ i ] )
pos += x % a[ i ];
else
pos += a[ i ];
pos = pos / b[ i ] + (bool)( pos % b[ i ] );
sum -= pos;
}
}
// cout << x << " - " << sum << "\n";
return sum >= 0;
}
main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
cin >> m;
for ( int i = 1; i <= n; i ++ )
cin >> a[ i ];
for ( int i = 1; i <= n; i ++ ) {
cin >> b[ i ];
if ( b[ i ] > a[ i ] )
a[ i ] = b[ i ];
}
int l, r, mid;
l = 1;
r = oo;
while ( r - l > 1 ) {
mid = ( l + r ) / 2;
if ( ok( mid ) )
l = mid;
else
r = mid - 1;
}
if ( ok( r ) )
l = r;
cout << l;
}
Compilation message (stderr)
Main.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
70 | main () {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |