#include <iostream>
#include <set>
#define int long long
using namespace std;
const int nmax = 3e5 + 7;
int v[nmax], b[nmax], cnt[nmax], n, k;
struct pairing {
int first, second;
const bool operator < (pairing a) const {
if(first != a.first) {
return first < a.first;
} else {
return second > a.second;
}
}
};
bool check(int x) {
int sum = x;
for(int i = 2; i <= n; i ++) {
int curr = (v[1] * x) / v[i];
if(v[i] * curr < v[1] * x) {
curr ++;
}
sum += curr;
}
if(sum <= n * k) {
return 1;
}
return 0;
}
int32_t main() {
cin >> n >> k;
for(int i = 1; i <= n; i ++) {
cin >> v[i];
}
for(int i = 1; i <= n; i ++){
cin >> b[i];
}
if(n * k > 3e5) {
sort(v + 1, v + n + 1);
int l = 0, r = n * k;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid) == 1) {
l = mid + 1;
} else {
r = mid;
}
}
while(check(r) == 0 && r > 0) {
r --;
}
while(check(r + 1) == 1) {
r ++;
}
cout << r;
return 0;
}
set<pairing> pq;
for(int i = 1; i <= n; i ++) {
pq.insert({max(v[i], b[i]), i});
cnt[i] = 1;
}
for(int i = 2; i <= k; i ++) {
for(int j = 1; j <= n; j ++) {
pairing curr = *(pq.begin());
int sum = curr.first, ind = curr.second;
pq.erase({sum, ind});
if(cnt[ind] < k) {
sum += max(v[ind], b[ind]);
cnt[ind] ++;
} else {
sum += b[ind];
}
pq.insert({sum, ind});
}
}
int minn = 1e18;
for(auto it : pq) {
// cout << it.first << " " << it.second << endl;
minn = min(minn, it.first);
}
cout << minn;
return 0;
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:46:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
46 | sort(v + 1, v + n + 1);
| ^~~~
| qsort
