Tuesday 4 August 2015

SPOJ SOLUTION - ALIEN AT THE TRAIN

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

int main()
{
    ull at,bt,tc,sum,i,j,count,max_count=0,cost;

    //get the number of test cases
    cin>>tc;
    while(tc--)
    {
        //get the at and bt
        cin>>at>>bt;
        ull arr[at];
        memset(arr,0,sizeof(arr));
        count=0;
        max_count=0;
        for(i=0;i<at;i++)
            cin>>arr[i];
        cost=100005;
        int start=0;
        sum=0;
        for(i=0;i<at;i++)
        {
           
            sum+=arr[i];
            count++;
            if(max_count<count&&sum<=bt||max_count==count&&sum<cost)
            {
                cost=sum;
                max_count=count;
            }
           
            while(sum>bt)
            {
                sum-=arr[start];
                count--;
                start++;
            }

            if(max_count<count&&sum<=bt||max_count==count&&sum<cost)
            {
                cost=sum;
                max_count=count;
            }
           
        }
        cout<<cost<<" "<<max_count<<"\n";
    }
    return 0;
}