QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202223#6632. Minimize Medianarseny_y#WA 110ms3824kbC++231.5kb2023-10-05 20:52:222023-10-05 20:52:22

Judging History

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

  • [2023-10-05 20:52:22]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:3824kb
  • [2023-10-05 20:52:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (auto &i : a) {
        cin >> i;
    }
    sort(a.begin(), a.end());
    vector<int> b(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
    }
    vector<int> dp(m * 4 + 1, LLONG_MAX);
    dp[1] = b[1];
    for (int i = 2; i <= m; ++i) {
        dp[i] = min(dp[i], b[i]);
        for (int j = 2; j <= m && i * j < dp.size(); ++j) {
            dp[i * j] = min(dp[i * j], dp[i] + b[j]);
        }
    }
    for (int i = (int)dp.size() - 2; i >= 1; --i) {
        dp[i] = min(dp[i], dp[i + 1]);
    }
    int l = -1, r = 1e9 + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (mid == 0) {
            int sm = 0;
            for (int i = 0; i <= n / 2; ++i) {
                sm += dp[a[i] + 1];
            }
            sm <= k ? r = mid : l = mid;
            continue;
        }
        auto na = a;
        int cnt = 0;
        int sm = 0;
        for (int i = 0; cnt <= n / 2; ++i, ++cnt) {
            if (a[i] <= mid) continue;
            int x = max(2LL, a[i] / mid - 10);
            while (a[i] / x > mid) {
                ++x;
            }
            sm += min(dp[a[i] + 1], dp[x]);
        }
        sm <= k ? r = mid : l = mid;
    }
    cout << r << '\n';
}

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

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: 110ms
memory: 3824kb

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
1
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
1
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 34th numbers differ - expected: '0', found: '1'