Computing Cost Of Array in java.

Given two length-$n$ arrays $a$ and $b$, we define the score by the dot product between them, i.e., ${\sum }_{i=1}^n{a}_i\ast b_i$. The original score is denoted as $S$
.
You can apply at most $2^{}$swaps to modify the array $a$. The cost of swaping $a_x$ and $a_y$ is $cost\left[a_x\right]\left[a_y\right]$. The total cost is denoted as $C$
.
After your swaps, we can recompute the score again, denoted as $S^{\prime }$
. The final score is $max(0,S^{\prime }-S-C)$. You want to maximize this score.

$\text{Input}$

The first line contains one number $n$
($1\le n\le 2^{18}$). The second line contains $n$ numbers - $a_1,a_2,a_3,\dots ,a_n$ ($0\le a_i<m$).
The third line contains $n$
numbers - $b_1,b_2,b_3,\dots ,b_n$ ($0\le b_i<2^{30}$). The fourth line contains one number $m$
($1\le m\le 512$). The next $m$ lines contains $m$ integers representing the matrix $cost\left[i\right]\left[j\right]$ ($0\le cost\left[i\right]\left[j\right]<2^{30},cost\left[i\right]\left[i\right]=0,cost\left[i\right]\left[j\right]=cost\left[j\right]\left[i\right]$).



$\text{Output}$

The first line contains one number $k$
($0\le k\le 2^{20}$) - the number of swaps. The next $k$ lines contains two numbers separated by space $u_i,v_i$ - signifying that at step $i$ you will swap values $a_{u_i},a_{v_i}$
$\text{Scoring}$
The final score is $max(0,S^{\prime }-S-C)$
. You want to maximize this score.

$\text{Tests}$
The will be in total $100$
tests with $4$ types of generation:
$\text{1.}$
$m=512$.
$\text{2.}$
$m=512$ and $70\%$ of values in matrix $cost$ are smaller than $2^{10}$.
$\text{3.}$
$m=64$.
$\text{4.}$
$m=512$ and $0\le b_i<2^{10}$ ($1\le i\le n$).

SAMPLE INPUT

3
2 1 0
1 2 3
3
0 1 1
1 0 1
1 1 0

SAMPLE OUTPUT

1
1 3

Explanation:

You swap indices $1$

and $3$ with cost $1$ and obtain the final sequence $[0,1,2]$. The final score score is $max(0,8-4-1)=3$.


SOLUTION: 


 import java.util.*;
public class CostOfArray {
    public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int ar1[]=new int[n];
int ar2[]=new int[n];
for(int i=0;i<n;i++){
    ar1[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
    ar2[i]=sc.nextInt();
}
int m=sc.nextInt();
int c[][]=new int[m][m];
for(int i=0;i<m;i++){
    for(int j=0;j<m;j++){
    c[i][j]=sc.nextInt();      
    }  
}
int sum=0;String mi="";int mk=0;ArrayList<String>al=new ArrayList<String>();
for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
        al.add(Integer.toString(i)+" "+Integer.toString(j));}}  
  
    List<String>  l=perms(al);
        //System.out.println("0"+ar1[i]+" "+ar1[j]);
    int ar4[]=new int[n];
    for(String ss:l){
        for(int i=0;i<n;i++){
        ar4[i]=ar1[i];  
        }
        StringTokenizer st1=new StringTokenizer(ss,"+");
        int ar3[]=new int[2];
        int sum3=0;int countz=0;String hj="";
        while(st1.hasMoreTokens()){
            countz++;
            String ss1=st1.nextToken();
            StringTokenizer st2=new StringTokenizer(ss1);
            int jk=0;
            while(st2.hasMoreTokens()){
                ar3[jk]=Integer.parseInt(st2.nextToken());
              
            jk++;
          
        }
            hj+=Integer.toString(ar3[0]+1)+" "+Integer.toString(ar3[1]+1)+"+";
        swap(ar4,ar3[0],ar3[1]);  
        sum3+=c[ar3[0]][ar3[1]];
    }

        //System.out.println("0"+ar1[i]+" "+ar1[j]);
    int    sum1=0;
    for(int ik=0;ik<n;ik++){
     sum1+=ar4[ik]*ar2[ik];
    }
    sum1-=sum3;
  
    if(sum<sum1){
        sum=sum1;
        mk=countz;
    mi=hj;}
    }
  


System.out.println(mk);
StringTokenizer stz=new StringTokenizer(mi,"+");
int nc=stz.countTokens();int jc=0;
while(stz.hasMoreTokens()){
    String njk=stz.nextToken();
        System.out.print(njk);  
        if(jc<nc-1)
            System.out.println();
    jc++;
}


}
    public static void swap(int ar1[],int a,int b){
    int k=ar1[a];
    //System.out.println("s"+k);
        ar1[a]=ar1[b];
        ar1[b]=k;
    }
    public static List<String> perms(ArrayList<String> al) {

        List<String> result = new ArrayList<String>();
    
        for (int width = 1; width <= al.size(); width++) { // for every length
            int stack[] = new int[width];
            for (int i = 0; i < stack.length; i++) { // start from a specific point without duplicates
                stack[i] = stack.length - i - 1;
            }
            int position = 0;
            while (position < width) {

                position = 0;
                StringBuilder sb = new StringBuilder();
                while (position < width) { // build the string
                    sb.append(al.get(stack[position])+"+");
                    position++;
                }
                result.add(sb.toString());
                position = 0;
                while (position < width) {
                    if (stack[position] < al.size() - 1) {
                        stack[position]++;
                        if (containsDuplicate(stack) == false)
                            break;
                        else
                            position = 0;
                    } else {
                        stack[position] = 0;
                        position++;
                    }
                }
            }
        }
        return result;
    }

    private static boolean containsDuplicate(int[] stack) {
        for (int i = 0; i < stack.length; i++) {
            for (int j = 0; j < stack.length; j++) {
                if (stack[i] == stack[j] && i != j) {
                    return true;
                }
            }
        }
        return false;
    }
  
}



Inputs and outputs:

1:
input:

3
2 1 0
1 2 3
3
0 1 1
1 0 1
1 1 0

output:
1
1 3

2:
input:
3
1 3 5
4 0 2
3
0 0 0
0 0 0
0 0 0





output:
2
2 3
1 2