I have written this code which has an execution time of 3.664 sec but the time limit is 3 seconds.
The question is this-
N teams participate in a league cricket tournament on Mars, where each
pair of distinct teams plays each other exactly once. Thus, there are a total
of (N × (N1))/2 matches. An expert has assigned a strength to each team,
a positive integer. Strangely, the Martian crowds love onesided matches
and the advertising revenue earned from a match is the absolute value of
the difference between the strengths of the two matches. Given the
strengths of the N teams, find the total advertising revenue earned from all
the matches.
Input format
Line 1 : A single integer, N.
Line 2 : N space separated integers, the strengths of the N teams.
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int stren[200000];
for(int a=0;a<n;a++)
cin>>stren[a];
long long rev=0;
for(int b=0;b<n;b++)
{
int pos=b;
for(int c=pos;c<n;c++)
{
if(stren[pos]>stren[c])
rev+=(long long)(stren[pos]-stren[c]);
else
rev+=(long long)(stren[c]-stren[pos]);
}
}
cout<<rev;
}
Rewrite your loop as:
sort(stren); for(int b=0;b<n;b++) { rev += (2 * b - n + 1) * static_cast<long long>(stren[b]); }
Why does it work
Your loops make all pairs of 2 numbers and add the difference to rev. So in a sorted array, bth item is subtracted (n-1-b) times and added b times. Hence the number
2 * b - n + 1
There can be 1 micro optimization that possibly is not needed:
sort(stren); for(int b = 0, m = 1 - n; b < n; b++, m += 2) { rev += m * static_cast<long long>(stren[b]); }