Optimize triplet summation
Can be done in \$O(n)\$ time

You can do better than \$O(n^3)\$ if you think about what kinds of triplets give nonzero contributions.  First of all, any triplet that does not contain a 1 will contribute zero to the final answer.  Next, if you examine all the triplets that contain 1, there are 5 types of triplets that contribute nonzero amounts to the answer:


1 1 1 contributes 3
1 1 2 contributes 2
1 1 X contributes 1, where X &gt; 2
1 2 2 contributes 1
1 2 3 contributes 1 


So you can get an \$O(n)\$ solution by counting all the 1s 2s and 3s in the input.  Then you can compute the number of each of the 5 types of triplets above by using simple combinatorics.

Sample \$O(n)\$ solution

Here is a sample solution based on the above.  Notice I removed the entire input array because all that is needed is the counts:

#include &lt;iostream&gt;

int main()
{
    long n   = 0;
    long c1  = 0;
    long c2  = 0;
    long c3  = 0;
    long res = 0;

    std::cin &gt;&gt; n;
    for(long i=0;i&lt;n;i++) {
        long num;
        std::cin &gt;&gt; num;
        if (num == 1)
            c1++;
        else if (num == 2)
            c2++;
        else if (num == 3)
            c3++;
    }

    // Count all the {1, 1, 1} triplets.  There are (c1 choose 3),
    // each contributing 3:
    res += ((c1 * (c1-1) * (c1-2)) / 6) * 3;

    // Count all the {1, 1, 2} triplets.  There are (c1 choose 2) * c2
    // combinations, each contributing 2:
    res += ((c1 * (c1-1)) / 2) * c2 * 2;

    // Count all the {1, 1, X} triplets, where X &gt; 2.  There are
    // (c1 choose 2) * (n - c1 - c2) combinations, each contributing 1:
    res += ((c1 * (c1-1)) / 2) * (n - c1 - c2);

    // Count all the {1, 2, 2} triplets.  There are c1 * (c2 choose 2)
    // combinations, each contributing 1:
    res += c1 * ((c2 * (c2-1)) / 2);

    // Count all the {1, 2, 3} triplets.  There are c1 * c2 * c3
    // combinations, each contributing 1:
    res += c1 * c2 * c3;

    std::cout &lt;&lt; res &lt;&lt; std::endl;
    return 0;
}


Of course, this program can be optimized even further by combining some of the expressions, but I wrote it in the way that most clearly demonstrates where each part of the answer came from.