| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 789022 | stefanneagu | Self Study (JOI22_ho_t2) | C++17 | 0 ms | 0 KiB |
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 <set>
#include <algorithm>
#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 = 0;
for(int i = 1; i <= n; i ++) {
int curr = x / v[i];
if(v[i] * curr < 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 = 1e18 * 2;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid) == 1) {
l = mid + 1;
} else {
r = mid;
}
}
while(check(r) == 0 && r > 1) {
r --;
}
while(check(r + 1) == 1) {
r ++;
}
cout << max(1, 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;
}