fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair < int , int >
  5. #define pb push_back
  6. #define mp make_pair
  7. #define mod 1000000009
  8. ll check(vector<int> &v ,vector<int> &c, int h){
  9.     ll sum = 0;
  10.     for(int i = 0 ; i < v.size() ; i++){
  11.         ll diff = abs(v[i] - h);
  12.         sum += diff*c[i];
  13.     }
  14.     return sum;
  15. }
  16. ll b_search(vector<int> &v , vector<int>&c){
  17.     ll low = 0 , mid , high = INT_MAX;
  18.     ll p , n , m , ans = LLONG_MAX;
  19.     while(low<high){
  20.         mid = (low+high)>>1;
  21.         //cout<<mid<<" ";
  22.         mid > 0 ? p = check(v , c , mid-1): INT_MAX;
  23.         //cout<<mid<<" "<<p<<" ";
  24.         m = check(v , c , mid);
  25.         n = check(v , c , mid+1);
  26.         if(ans == m)
  27.             break;
  28.         ans = min(ans , m);
  29.         if(p <= m)
  30.             high = mid+1;
  31.         else if(n <= m)
  32.             low = mid;
  33.     }
  34.     return ans;
  35. }
  36. int main(){
  37.  
  38.     int t;
  39.     scanf("%d" , &t);
  40.     while(t--){
  41.         int n , temp;
  42.         scanf("%d",&n);
  43.         vector<int> v(n) , c(n);
  44.         for(int i = 0 ; i < n ; i++){
  45.             scanf("%d",&temp);
  46.             v[i] = temp;
  47.         }
  48.         for(int i = 0 ; i < n ; i++){
  49.             scanf("%d",&temp);
  50.             c[i] = temp;
  51.         }
  52.         printf("%lld\n", b_search(v , c));
  53.     }
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1 
5
2 4 6 8 9
10 30 40 50 80
stdout
copy 
340
https://ideone.com/wb7xjt
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!