needed help on spoj problem KOPC12A - K12 - Building Construction

link text

 #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

my answer is coming 390.
but by manual calculation it should be 340 for h=8.

can you please post your code in ideone and share the link? It is unreadable.

please see the code on below link

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

thanks for help

Fixed formatting.

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;
}

}