QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#174483 | #6632. Minimize Median | PERAPRO# | TL | 1ms | 8696kb | C++20 | 2.9kb | 2023-09-10 08:09:40 | 2023-09-10 08:09:41 |
Judging History
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 ...