QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #127699 | #6632. Minimize Median | winoua | ML | 657ms | 126892kb | C++14 | 2.1kb | 2023-07-19 22:23:13 | 2023-07-19 22:23:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
int x = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
for(x = ch ^ 48 ; isdigit(ch = getchar()) ; x = (x << 3) + (x << 1) + (ch ^ 48));
return x * f;
}
const int N = 1e6 + 9;
int n,m,k,a[N],mx;
ll c[N * 2],d[N * 2],b[N];
vector<int> factor[N * 2]; ll minx=1e18;
void solve(){
minx = 1e18 + 10;
for(int i = 1 ; i <= mx ; i ++) factor[i].clear();
for(int i = m + 1 ; i <= mx ; i ++) c[i] = minx;
for(int i=1;i<=mx;i++){
for(int j=1;j<=mx/i;j++)
factor[i*j].push_back(i);
}
for(int i=1;i<=mx;i++){
for(auto it:factor[i]){
int w=i/it;
c[i]=min(c[i],c[it]+c[w]);
}
}
//for(int i = 1 ; i <= mx ; i ++) cout<<c[i]<<" ";
//cout<<"\n";
}
bool judge(int mid){
int num = 0; ll ans = 0;
//cout<<mid<<" -- > "<<"\n";
for(int i = 1 ; i <= n ; i ++){
if(a[i] >= mid) {
int kk = a[i] / mid + 2;
//cout<<kk<<"\n";
while(kk > 1 && floor(a[i] / (kk - 1)) < mid) kk --;
b[++num] = c[kk];
//cout<<a[i]<<" "<<kk<<" "<<c[kk]<<"\n";
}
}
sort(b + 1,b + num + 1);
for(int i = 1 ; i <= num - (n / 2) ; i ++) ans += b[i];
//cout<<" -- > "<<ans<<"\n";
if(ans <= k) return true;
return false;
}
signed main(){
int T = read();
while(T --){
n = read(), m = read(), k = read(), mx = m;
for(int i = 1 ; i <= n ; i ++) a[i] = read(), mx = max(mx,a[i]);
for(int i = 1 ; i <= m ; i ++) c[i] = read();
mx = mx * 2;
solve(); c[1] = 0; d[mx] = c[mx]; ll as = 1e18;
for(int i = mx - 1 ; i >= 1 ; i --) d[i] = min(c[i],d[i + 1]);
for(int i = 1 ; i <= mx ; i ++) as = min(as,c[i] + d[(int)ceil(mx / i)]);
for(int i = 1 ; i <= mx ; i ++) c[i] = min(d[i],as);
//for(int i = 1 ; i <= mx ; i ++) cout<<c[i]<<" "; cout<<"\n";
sort(a + 1,a + n + 1);
int l = 1, r = a[(n / 2) + 1] + 1, ans = r;
while(l <= r){
int mid = (l + r) >> 1;
if(judge(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout<<ans - 1<<"\n";
}
return 0;
}
/*
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 56912kb
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
output:
2 2 1
result:
ok 3 number(s): "2 2 1"
Test #2:
score: 0
Accepted
time: 57ms
memory: 57076kb
input:
100000 5 10 5 3 7 1 10 10 11 6 11 6 1 8 9 1 3 1 5 6 51 2 2 2 5 1 42 61 26 59 100 54 5 10 76 7 5 8 4 7 97 4 44 83 61 45 24 88 44 44 5 8 90 1 1 5 1 3 35 15 53 97 71 83 26 7 5 3 52 1 1 3 1 1 22 6 93 5 6 28 6 6 1 3 1 9 31 2 19 10 27 5 8 31 3 6 2 1 2 32 29 13 7 57 34 9 5 5 6 75 3 3 4 5 4 40 56 38 60 17 3...
output:
0 2 0 0 0 0 0 0 3 4 0 0 0 0 1 1 0 0 0 0 1 1 0 2 2 0 0 0 0 0 2 0 0 0 2 2 0 1 0 0 0 0 1 0 2 4 1 1 0 0 2 0 0 7 0 1 0 0 0 1 1 0 1 0 1 0 0 2 1 0 6 3 0 0 1 0 2 0 0 3 0 1 0 1 0 2 0 0 0 0 1 2 1 4 0 0 0 0 0 0 1 2 2 1 2 2 0 1 1 0 0 0 0 0 1 2 1 4 1 0 4 1 2 1 0 0 0 0 1 2 1 0 0 2 3 1 0 1 1 1 0 1 5 0 1 2 0 2 0 0 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 33ms
memory: 57964kb
input:
30000 11 7 88 4 6 1 2 1 7 3 3 2 6 3 44 60 14 92 55 88 13 11 11 36 8 9 2 9 1 7 1 7 9 3 8 67 13 49 55 23 18 45 33 8 8 66 11 8 10 3 4 6 3 5 3 1 1 7 5 7 4 14 12 15 21 15 11 7 11 5 65 1 5 3 3 5 1 3 4 5 5 1 27 22 18 56 53 11 8 31 7 6 4 3 1 2 5 1 3 2 7 56 64 56 52 1 10 42 38 11 6 90 6 1 5 3 6 2 2 2 3 1 1 8...
output:
0 1 3 1 0 1 0 1 1 1 1 0 2 1 0 2 2 6 0 0 0 3 1 2 1 1 0 0 2 0 1 6 2 0 0 0 0 2 0 0 0 0 2 1 2 1 0 1 0 0 0 1 1 2 5 1 0 0 7 3 1 3 3 2 0 0 0 3 2 2 0 2 2 3 0 1 0 7 4 0 3 0 1 1 5 0 4 1 4 0 1 2 4 0 2 1 0 1 0 0 4 0 0 2 1 0 0 1 0 1 0 0 0 1 1 0 0 5 2 0 0 0 2 0 0 0 2 0 0 0 0 0 1 1 2 3 1 0 0 0 4 4 0 2 0 3 4 0 1 1 ...
result:
ok 30000 numbers
Test #4:
score: 0
Accepted
time: 28ms
memory: 56968kb
input:
10000 21 2 301 2 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 1 2 1 1 2 91 73 21 16 233 1 6 6 8 10 10 9 3 8 8 8 7 11 6 7 11 9 13 13 11 11 29 88 36 42 98 53 65 44 31 58 27 36 34 51 33 26 21 35 699 11 33 22 24 34 33 24 16 5 12 8 26 34 4 1 33 10 3 9 21 10 56 27 39 44 44 53 75 14 57 20 51 69 85 15 29 50 76 79 37 6 17 ...
output:
1 6 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 11 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 453ms
memory: 75892kb
input:
10 99999 48959 549895809 17383 33522 48377 31386 19330 13043 27394 37249 36294 12722 8373 37625 12026 13690 14053 30528 16342 31971 17759 23330 19377 6906 2676 9898 35581 3357 38474 28896 7227 46575 20055 8860 38630 48009 37394 20074 31995 24762 36589 33677 5802 16186 22579 2830 43898 14963 41255 30...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 657ms
memory: 126892kb
input:
1 999999 293797 278478314 67762 104009 176376 207621 189337 131231 23909 205140 207710 179872 138897 128633 199664 237425 193080 187398 13587 257639 152428 246508 123562 143881 26620 119039 114584 74242 194355 237441 149776 20279 184277 170447 262736 145607 92710 99452 283332 188967 257554 248224 67...
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Memory Limit Exceeded
input:
1 99999 1000000 709380 3515 30629 61254 18266 46934 53061 981 63751 4639 35121 72295 47911 56251 13323 17732 6035 51729 57468 5653 91728 22114 69445 54695 7726 74817 142 14101 43678 58715 9895 1984 71046 93603 95882 53070 17490 50060 77935 92407 26483 91683 76316 73977 83427 70507 11756 85938 49558 ...