Gfrktyl

Code Chef Problem description

You are given a sequence of $N$ powers of an integer $k$; let's denote the $i$-th of these powers by $k^{A_i}$.
You should partition this sequence into two non-empty contiguous subsequences; each element of the original sequence should appear in exactly one of these subsequences.
In addition, the product of (the sum of elements of the left subsequence) and (the sum of elements of the right subsequence) should be maximum possible.

Find the smallest position at which you should split this sequence in such a way that this product is maximized.

I am basically finding all possible partitions and finding the minimum index of the maximum product. This doesn't work because of the following constraints to input:

$1 leq t leq 10$
$2 leq n leq 10^5$
$2 leq k leq 10^9$
$0 leq A_i leq 10^5$

My algorithm seems to work for smaller numbers as it passes the test case:

Input

1

5 2

1 1 3 3 5

Output

4

It fails as there is no way to store $k^{A_i}$

This is how I implemented it,

#include <iostream>

#include <cmath>



typedef unsigned long ul;

typedef unsigned long long ull;



int main()

{

    int t, n;

    ull k, *a;

    std::cin >> t; //No. of testcases

    while(t--)

    {

        std::cin >> n >> k;

        a = new ull[n];

        for(int i = 0; i < n; i++)

        {

            std::cin >> a[i];

        }

        int max_index = 1;

        ull n1, n2;

        n1 = pow(k, a[0]); //Wont work for all cases (mentioned in the constraints)

        n2 = pow(k, a[1]);

        for(int i = 2; i < n; i++)

        {

            n2 += pow(k, a[i]);

        }

        ull max_product = n1 * n2;

        for(int i = 1; i < n - 1; i++)

        {

            ull x = pow(k, a[i]);

            n1 += x;

            n2 -= x;

            ull product = n1 * n2;

            if(product > max_product)

            {

                max_product = product;

                max_index = i + 1;

            }

        }

        delete a;

        std::cout << max_index << "n";

    }

    return 0;

}

I understand that a completely different algorithm is expected. I can't think of such an algorithm.