QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734020#6632. Minimize MedianVedant18#WA 96ms3560kbC++232.7kb2024-11-10 23:07:032024-11-10 23:07:03

Judging History

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

  • [2024-11-10 23:07:03]
  • 评测
  • 测评结果:WA
  • 用时:96ms
  • 内存:3560kb
  • [2024-11-10 23:07:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++)                // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++)               // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++)               // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++)               // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--)                // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--)                // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--)                // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--)                // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--)                       // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i]       // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
#define vll vector<ll>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))

#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
    FAST
    tt{
        ll n,m,k;
        cin>>n>>m>>k;
        inv(a,n);
        inv(cst,m);
        inr(m-1,1){
            cst[i]=min(cst[i],cst[i+1]);
        }
        cst[1]=0;
        for(ll i=2;i<=m;i++){
            for(ll j=2;j<=(m)/i;j++){
                cst[j*i]=min(cst[j*i],cst[j]+cst[i]);
            }
        }
        inr(m-1,1){
            cst[i]=min(cst[i],cst[i+1]);
        }
        ll lo=1;
        ll hi=m;
        auto ok=[&](int md)->bool{
            //can i make more than (n)/2 elements less than md
            vll cc;
            in(1,n){
                    ll x=(a[i]+md-1)/md;
                    cc.push_back(cst[x]);
            }

            sort(all(cc));
            ll tcst=0;
            for(int i=0;i<((n+1)/2);i++){
                tcst+=cc[i];
            }
            return (tcst<=k);
        }
        ;
        // ok(3);
        ll ans=m;
        while(lo<=hi){
            ll mid=(lo+hi)/2;
            if(ok(mid)){
                ans=mid;hi=mid-1;
            }
            else{
                lo=mid+1;
            }
        }
        cout<<ans<<endl;
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
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: 96ms
memory: 3560kb

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:

1
2
1
1
1
1
1
1
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
2
1
1
1
2
2
1
1
1
1
1
1
1
1
2
4
1
1
1
1
2
1
1
7
1
2
1
1
1
1
1
1
1
1
1
1
1
2
1
1
6
3
1
1
1
1
2
1
1
3
1
1
1
1
1
2
1
1
1
1
1
2
2
4
1
1
1
1
1
1
1
2
2
1
2
2
1
1
1
1
1
1
1
1
1
2
1
4
1
1
4
1
2
1
1
1
1
1
1
2
1
1
1
2
3
1
1
1
1
1
1
1
5
1
1
2
1
2
1
1
...

result:

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