oj.uz

Submission #625166

# Submission time Handle Problem Language Result Execution time Memory
625166 2022-08-09T14:10:41 Z iomoon191 Self Study (JOI22_ho_t2) C++17
0 / 100
 1000 ms 212 KB 
#include <bits/stdc++.h>
using ll = long long;
// #define int ll
using namespace std;

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353

#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

const ll N = 500005;
const ll inf = 1e18;

ll n, m, a[N], b[N];

bool chk(ll x){
	ll res = 0;
	foru(i, 1, n){
		if(a[i] > b[i]){
			ll z = (x + a[i] - 1) / a[i];
			z = min(z, m);
			ll nw = inf;
			foru(j, max(z - 2, 0ll), z){
				ll rem = max(x - a[i] * j, 0ll);
				nw = min(nw, j + (rem + b[i] - 1) / b[i]);
			}
			res += nw;
		}
		else{
			res += (x + b[i] - 1) / b[i];
		}
		if(res > m * n) return false;
	}
	return true;
}

void solve(){
	cin >> n >> m;
	foru(i, 1, n) cin >> a[i];
	foru(i, 1, n) cin >> b[i];
	ll l = 0, r = inf;
	while(l != r){
		ll mid = l + r >> 1;
		if(chk(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1; 
	while(t--){
		solve();
	}
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   ll mid = l + r >> 1;
      |            ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -