How can I optimize this code in O(n²) time complexity.

Question

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define ll long int
#define mod 1000
#define for1(i,k,n) for(ll i=k;i<n;i++)
#define for2(k,n) for(ll j=k;j<n;j++)
#define E cout<<endl;
#define e endl;
#define maxn 10001

int main()
{
#ifndef ONLINE_JUDGE
clock_t tStart = clock();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

ios_base:: sync_with_stdio(false);
cin.tie(0);
////////////////////////////////////// start.................

ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll arr[n];
ll i, j, k, temp = 0, sum = 0, cnt = 0;// here cnt counts number of swaps
arr[0] = 0;
for (i = 1; i <= n; i++) {
arr[i] = i;

sum += i;
}
for (i = 1; i < n; i++)
{
for (k = i + 1; k <= n; k++)
{
swap(arr[i], arr[k]);
ll sumt = sum;
temp = 0;
for (j = 1; j <= n; j++)
{
sumt -= arr[j];
temp += arr[j];
if (sumt < temp)
break;
else if (sumt

Answer 1

Similar to coder :p