QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131250 | #6632. Minimize Median | stasio6# | WA | 174ms | 7572kb | C++14 | 1.5kb | 2023-07-26 19:42:10 | 2023-07-26 19:42:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int _,n,m,k,a[1<<20],c[1<<20],f[1<<20],l,r,d;
int C(int x){
int s=0;
for(int i=1;i<=n/2+1;i++)
s+=f[a[i]/(x+1)+1];
return s<=k;
}
void Z(){
cin>>n>>m>>k,l=0,r=m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>c[i];
m++,c[m]=f[m]=2e9,sort(a+1,a+n+1);
for(int i=m-1;i;i--)
c[i]=min(c[i],c[i+1]),f[i]=c[i];
f[1]=0;
f[0]=0;
int maxf = 1000000000000000001ll, infj = m;
for(int i=2;i<=m;i++) {
int maxj = m / i + 1;
while (infj > maxj) {
cmn(maxf, f[infj]);
infj--;
}
cmn(f[maxj], maxf);
for (int j = maxj - 1; j > 0; j--) {
cmn(f[j], f[j + 1]);
}
for (int j = 1; j <= maxj; j++) {
f[min(m, i * j)] = min(f[min(m, i * j)], f[j] + c[i]);
if (i * j > infj) {
cmn(maxf, f[j] + c[i]);
}
}
}
for(int i=m-1;i;i--)
f[i]=min(f[i],f[i+1]);
// for(int i=1;i<=m;i++)
// cout<<f[i]<<" \n"[i==m];
while(l<r)
d=(l+r)/2,C(d)?r=d:l=d+1;
cout<<l<<'\n';
}
signed main() {
ios::sync_with_stdio(0);
for(cin>>_;_--;)
Z();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7524kb
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: -100
Wrong Answer
time: 174ms
memory: 7572kb
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:
wrong answer 2716th numbers differ - expected: '0', found: '1'