Help me in zco13001

help
1

CONSTRAINT –

8
8697×158 10.5 KB

PROBLEM - Tournament - Problems - CodeChef

#include<bits/stdc++.h>
using namespace std;
/*#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;
	//use cerr if u want to display at the bottom
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif*/
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    unsigned long long n;
    cin>>n;
vector<unsigned long long> v;
int r=0;
for(unsigned long long i=1;i<=n;i++){
    unsigned long long g;
    cin>>g;
 v.push_back(g);
 
}

int no_matches = (n*(n-1))/2;

   for(unsigned long long i=1;i<n;i++){
       for(long long j=i+1;j<=n;j++){
       
       
       if(v[i-1]>=v[j-1]){
           r +=  (v[i-1]-v[j-1]);
       }
         else{
             r += (v[j-1]-v[i-1]);
         }
        
       
   } 
}
  cout<<r;
    
    
}

7
71346×571 31.4 KB

2

@abhaypandey114
u r getting tle bcoz for higher value of n O(n^2) is high time complexity thus u have to reduce the time complexity lesser than O(n^2) .
I have coded in O(nlogn) time in a much simpler way hope u will get it.
include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int n;
cin>>n;
long long int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
map<long long int ,long long int> mp;
long long int sm=0;
for(int i=0;i<n;i++)
{
sm+=a[i];
mp[i]=sm;
}
long long int ans=0;
for(int i=0;i<n;i++)
{
ans+=(((i+1)*a[i])-mp[i]);
ans+=(mp[n-1]-mp[i]-((n-1-i)*a[i]));
}
cout<<ans/2;
return 0;
}