QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132788#6632. Minimize MedianRabeya#WA 79ms5584kbC++141.8kb2023-07-31 16:19:012023-07-31 16:19:05

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-31 16:19:05]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:5584kb
  • [2023-07-31 16:19:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

const int N = 2e6 + 5;
int a[N], cost[N];

void solve() {
    int n, m, k;
    cin>> n >> m >> k;

    for(int i=1; i<=n; i++) cin>> a[i];
    for(int i=1; i<=m; i++) cin>> cost[i];

    sort(a+1, a+n+1);

    vector<int> b;
    vector<int> c;
    vector<int> div;
    for(int i=1; i<=(n+1)/2; i++) b.push_back(a[i]);
    int mn = 1e9+5;
    for(int i=m; i>=2; i--) {
        if(cost[i] >= mn) continue;
        mn = cost[i];
        c.push_back(cost[i]);
        div.push_back(i);
    }
    reverse(c.begin(), c.end());
    reverse(div.begin(), div.end());

    if(c.size() == 0) {
        cout<< b.back() << endl;
        return;
    }

    int ans = b.back();
    int l = 0, r = ans;
    while(l <= r) {
        int mid = (l+r)>>1;
        vector<int> dp(m+3, 1e9+5);
        dp[mid] = 0;
        int pos = 0;
        for(int i=mid+1; i<=m; i++) {
            dp[i] = c[pos];
            if(i/div[pos] > mid) dp[i] += dp[i/div[pos]];

            while(pos + 1 < c.size()) {
                int costnext;
                costnext = c[pos+1];
                if(i/div[pos+1] > mid) costnext += dp[i/div[pos+1]];
                if(costnext <= dp[i]) {
                    dp[i] = costnext;
                    pos++;
                }
                else break;
            }
        }
        int need = 0;
        for(int e: b) {
            if(e > mid) need += dp[e];
        }
        if(need <= k) {
            ans = min(ans, mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout<< ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>> t;
    while(t--) {
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5584kb

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: 79ms
memory: 5512kb

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
1
...

result:

wrong answer 150th numbers differ - expected: '0', found: '1'