QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127246#6632. Minimize MedianEthan_xu#WA 82ms3548kbC++202.1kb2023-07-19 14:40:052023-07-19 14:40:09

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-19 14:40:09]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:3548kb
  • [2023-07-19 14:40:05]
  • 提交

answer

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

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;


    int T ;
    cin >> T ;
    while(T --)
    {
        int n , m , k ;
        cin >> n >> m >> k ;
        vector<int> a(n + 1 , 0) ;
        for(int i = 1 ; i <= n ; i ++)  cin >> a[i] ;
        vector<int> cost(m + 2 , 0) ;
        for(int i = 1 ; i <= m ; i ++)  cin >> cost[i] ;
        cost[m + 1] = k + 1 ;
        for(int i = m - 1 ; i >= 1 ; i --)  cost[i] = min(cost[i] , cost[i + 1]) ;
        for(int i = 2 ; i <= m ; i ++)
        {
            int pp = min(i - 1 , (int)sqrt(i) + 2) ;
            for(int j = 1 ; j <= pp ; j ++)
                cost[i] = min(cost[i] , cost[j] + cost[(i + j - 1) / j]) ;
        }
        for(int i = m - 1 ; i >= 1 ; i --)  cost[i] = min(cost[i] , cost[i + 1]) ;
        int ppp = k + 1 ;
        for(int i = 2 ; i <= m - 1 ; i ++)  ppp = min(ppp , cost[i] + cost[(m + i - 1) / i]) ;
        cost[m] = min(cost[m] , ppp) ;
        for(int i = m - 1 ; i >= 1 ; i --)  cost[i] = min(cost[i] , cost[i + 1]) ;
        // cost[i] 表示使用了若干个炸弹,形成的伤害至少是i的最小代价和
        
        int l = 0 , r = m ;
        int res = r ;
        auto ok = [&](int x)
        {
            int p = n / 2 ;
            vector<int> v ;
            for(int i = 1 ; i <= n ; i ++)
                if(a[i] > x)
                    v.push_back(a[i]) ;
            if(v.size() <= p)  return true ;
            sort(v.begin() , v.end()) ;
            int cur = v.size() ;
            int t = k ;
            for(auto u : v)
            {
                int z = (u + 1 + x) / (x + 1) ; // u / z <= x
                assert(z <= m + 1) ;
                if(cost[z] <= t)  t -= cost[z] , cur -= 1 ;
                else  break ;
            }
            return cur <= p ;
        } ;
        while(l <= r)
        {
            int mid = (l + r) / 2 ;
            if(ok(mid))  res = mid , r = mid - 1 ;
            else  l = mid + 1 ;
        }
        cout << res << '\n' ;
    }

    return 0 ;
}
/*



*/

詳細信息

Test #1:

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

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: 82ms
memory: 3448kb

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'