QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#174483#6632. Minimize MedianPERAPRO#TL 1ms8696kbC++202.9kb2023-09-10 08:09:402023-09-10 08:09:41

Judging History

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

  • [2023-09-10 08:09:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:8696kb
  • [2023-09-10 08:09:40]
  • 提交

answer

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(), s.end()
#define mp make_pair
#define int long long
#define ll long long
// typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
char el = '\n';
char esp = ' ';


int cost [1000001] ; 
int cont [1000001] ; 
int ans [1000001] ; 
int n , m , c ; 
bool bus ( int h ){
    bool visit [1000001] ; 
    int sum1 = 0 ; 
    for ( int i = 0 ; i <= m ; i++ ) visit [i] = 0 ;  
    int cont1 = 0 ; 
    priority_queue < pair < int , int > > q ; 
    for ( int i = 1 ; i <= h ; i++ ){
        q.push ( { 0 , i } ) ;
    }
    while ( !q.empty(  ) ){
        pair < int , int > k = q.top ( ) ;
        q.pop ( ) ;
        if ( visit [k.second] ) continue ; 
        visit [k.second] = true ;
        ans[k.second] = -k.first ;
        for ( int i = 0 ; i < cont[k.second] ; i++ ){
            sum1 += ans[k.second] ; 
            cont1++ ; 
            if ( sum1 > c ) return false;
            if ( cont1 == n / 2 + 1 ) return true ; 
        }
        for ( int i = 2 ; i < m ; i++ ){
            int p = k.second * i ; 
            int sum = - ( (- ( k.first)) + cost[i] ) ; 
            if ( p > m ) break ; 
            for ( int d = 0 ; d < i ; d++ ){
                if ( p + d > m ) break ; 
                q.push (  {sum , p + d }) ;               
            }
        }
    }
    return false ; 
}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
ostream& operator<<(ostream& os, const vector<T> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

int32_t main(){
	fast_io;
	/*
 	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    int tc;
    cin>>tc;
    
    while(tc--){

        cin>>n>>m>>c ; 
        for ( int i = 0 ; i <= m ; i++ ) cont [i] = 0 ; 
        for ( int i = 0 ; i < n ; i++ ){
            int a ; 
            cin>>a ;
            cont[a]++ ; 
        }
        for ( int i = 1 ;i <= m ;i++){
            int a ; 
            cin>>a ; 
            cost[i] = a  ; 
        }
        int lo = 1 ;
        int hi = m ; 
        int best = INT_MAX ; 
        while ( lo  <= hi ){
            int mid = ( lo + hi ) / 2 ;
            if ( bus ( mid ) ){
                best = min ( best , mid ) ; 
                hi = mid - 1  ; 
            }
            else{
                lo = mid + 1 ; 
            }
        }
        cout<<best<<endl ; 
    }

}

/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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
3
3
4
2
4
1
1
3
1
1
2
1
1
3
1
1
2
2
1
2
3
1
1
2
1
1
6
2
2
2
1
1
3
1
1
1
1
2
4
1
1
2
1
2
1
1
8
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
6
4
1
1
1
1
2
1
1
3
1
1
1
1
2
2
1
1
1
1
1
2
1
4
1
1
4
1
1
1
1
2
2
1
2
2
1
1
1
1
1
1
1
1
1
2
2
4
3
1
4
1
2
1
2
3
1
1
1
2
1
6
1
2
3
1
1
1
1
1
2
1
5
1
1
2
3
2
1
1
...

result: