Header Ads Widget

Thief and Warehouses | Hackerearth practice problem solution

Rajnish Tripathi 06:47

   Problem:-

There are N warehouses. The warehouses are located in a straight line and are indexed from 1 to N. Each warehouse contains some number of sacks.

A thief decides to rob these warehouses. Thief figured out that he can escape the police if and only if he follows both the following 2 constraints:

  • He will rob only one continuous segment of warehouses.
  • He will rob same number of sacks from each warehouse.

Thief wants to calculate the maximum number of sacks he can steal without getting caught by the police.

Input Format:

The first line contains an integer T denoting number test cases.

The first line of each test case contains a single integer N denoting number of warehouses.

The second line of each test case contains N space-separated integers :a[1],a[2],a[3]...a[n].a[i] denotes number of sacks in ith warehouse.

Constraints:

  • 1<=T<=5
  • 1<=N<=106
  • 0<=A[i]<=1012

Output Format:

Output exactly T lines.

The ith line should contain a single integer, i.e the answer for ith testcase(maximum number of sacks thief can steal without getting caught).

Sample Input
2
5
2 4 3 2 1
6
3 0 5 4 4 4
Sample Output
8
16
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In first test case thief will steal 2 sacks from each warehouse from 1 to 4.

10

Code:-

 you can submit this solution  by using the language c++, c++14 and c++17.

In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
cin.tie(NULL);
    cout.tie(NULL);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        long int a[n];
        //taking input
        for(int i=0;i<n;i++)
         cin>>a[i];
        long int total,max=0;
        for(int i=0;i<n;i++)
        {
            long int min=a[i];
            total=a[i];
            if(min!=0)
            {
                //if previous value is less than the
                // min then we have to also include the
                //prevoius value until it less than min
             if(a[i]<a[i-1] && i!=0)
                {
                    for(int l=i-1;l>=0;l--)
                    {
                        if(a[l]<min)
                         break;
                        total+=min;
                    }
                }
                // check form i to last element
                // and add it to total until min sacks are
                //possible to take from warehouses
             for(int j=i+1;j<n;j++)
             {
                 if(a[j]<min)
                        break;
                    total+=min;
                }
                // if max is less total
                if(max<total)
                    max=total;
            
            }
        }
        cout<<max<<endl;
    }
}

Recommended Post:-

         MCQs:-
Tags:

Post a Comment

0 Comments