needed help on spoj problem KOPC12A - K12 - Building Construction

`````` #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
ll check(vector<int> &v ,vector<int> &c, int h){
ll sum = 0;
for(int i = 0 ; i < v.size() ; i++){
ll diff = abs(v[i] - h);
sum += diff*c[i];
}
return sum;
}
ll b_search(vector<int> &v , vector<int>&c){
ll low = 0 , mid , high = INT_MAX;
ll p , n , m , ans = LLONG_MAX;
while(low<high){
mid = (low+high)>>1;
mid > 0 ? p = check(v , c , mid-1): INT_MAX;
m = check(v , c , mid);
n = check(v , c , mid+1);
if(ans == m)
break;
ans = min(ans , m);
if(p <= m)
high = mid;
else if(n <= m)
low = mid+1;
}
return ans;
}
int main(){

int t;
scanf("%d" , &t);
while(t--){
int n , temp;
scanf("%d",&n);
vector<int> v(n) , c(n);
for(int i = 0 ; i < n ; i++){
scanf("%d",&temp);
v[i] = temp;
}
for(int i = 0 ; i < n ; i++){
scanf("%d",&temp);
c[i] = temp;
}
printf("%lld\n", b_search(v , c));
}

return 0;
}
``````

for the test case

``````1
5
2 4 6 8 9
10 30 40 50 80
``````

but by manual calculation it should be 340 for h=8.

The high in the binary search search must be set to mid+1 when p<=m and low must be set to mid when n<=m.Here is your AC solution.Here

My code also works.

``````    import java.util.*;
public class KOPC12A {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int t=s.nextInt();
while(t--!=0)
{
int n=s.nextInt();
int heights[]=new int[n];
int costs[]=new int[n];
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++)
{
heights[i]=s.nextInt();
max=Math.max(max, heights[i]);
}
for(int i=0;i<n;i++)
{
costs[i]=s.nextInt();
}

int l=0,h=max;
long ans=Long.MAX_VALUE;
while(l<=h)
{
int mid=(l+h)/2;
long amid1=cost(heights,costs,mid);
long amid2=Long.MAX_VALUE;
if(mid+1<=max)
amid2=cost(heights,costs,mid+1);

ans=Math.min(ans, amid1);
if(amid2<amid1)
{
l=mid+1;
}
else
{
h=mid-1;
}

}
System.out.println(ans);
}

}

public static long cost(int[] heights,int[] costs, int height)
{
long sum=0;
for(int i=0;i<heights.length;i++)
{
sum+=Math.abs(heights[i]-height)*costs[i];
}
return sum;
}
``````

}