QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200576 | #6632. Minimize Median | hacker_john | RE | 0ms | 0kb | C++14 | 2.0kb | 2023-10-04 17:38:28 | 2023-10-04 17:38:29 |
answer
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define int long long
#define pb push_back
#define LL long long
#define endl "\n"
const int N = 1e6 + 10;
const int INF = 1e10;
using namespace std;
int a[N], b[N], n, m, k;
inline bool check(int haha) {
int sum = 0;
for (register int i = 1; i <= (n + 1) / 2; i ++ ) {
if(a[i] <= haha) continue;
int tmp1 = ceil(1.0 * a[i] / haha), tmp2 = a[i] / haha;
int tmp;
if(haha >= a[i] / tmp2) tmp = tmp2;
else tmp = tmp1;
sum += b[tmp];
}
if(sum <= k) return true;
return false;
}
inline bool t_check() {
int sum = 0;
for (register int i = 1; i <= (n + 1) / 2; i ++ ) {
sum += b[a[i] + 1];
}
if(sum <= k) return true;
return false;
}
void solve(){
std::cin >> n >> m >> k;
for (register int i = 1; i <= n; i ++ ) {
std::cin >> a[i];
}
std::sort(a + 1, a + n + 1);
for (register int i = 1; i <= m; i ++ ) {
std::cin >> b[i];
}
for (register int i = m; i >= 1; i -- ) b[i] = std::min(b[i], b[i + 1]);
for (register int i = 2; i <= m; i ++ ) {
int mm = m / b[i];
mm = std::min(mm, i);
for (register int j = 2; j <= mm; j ++ ) {
b[i * j] = std::min(b[i * j], b[j] + b[i]);
}
}
b[m + 1] = INF;
for (register int i = 2; i <= m; i ++ ) b[m + 1] = std::min(b[m + 1], b[i] + b[(int)ceil(1.0 * (m + 1) / i)]);
for (register int i = m - 1; i >= 1; i -- ) {
b[i] = std::min(b[i], b[i + 1]);
}
int l = 1, r = INF;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(t_check()) l = 0;
std::cout << l << '\n';
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int T;
T = 1;
std::cin >> T;
while(T --) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 3 5 0 2 5 2 3 2 4 6 13 3 5 3 2 5 3 3 2 4 6 13 3 5 6 2 5 2 3 2 4 6 13