QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131250#6632. Minimize Medianstasio6#WA 174ms7572kbC++141.5kb2023-07-26 19:42:102023-07-26 19:42:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-26 19:42:12]
  • 评测
  • 测评结果:WA
  • 用时:174ms
  • 内存:7572kb
  • [2023-07-26 19:42:10]
  • 提交

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'