SPOJ (MIXTURES)

#include<bits/stdc++.h>
using namespace std;
long long int min_mul(long long int arr[],long long int n)
{
long long int smok,s;
long long int l,i,j,k,max_val=1000000;

long long int dp[n+1][n+1],dp_smoke[n+1][n+1];

for( i=0;i<=n;i++)
{
    for( j=0;j<=n;j++)
    {
        dp[i][j]=0;
        dp_smoke[i][j]=0;
    }

}



  for(i=1;i<=n;i++)
  dp[i][i]=arr[i];



for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
    {
          j=i+l-1;
          dp[i][j]=INT_MAX;

         smok=INT_MAX;

       for(k=i;k<=j-1;k++)//diagonal
       {

            if(smok>dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j])
{
    smok=dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j];
    s=k;

}

       }

       dp[i][j]=(dp[i][s]+dp[s+1][j])%100;
       dp_smoke[i][j]=smok;
    }
}


/*
for(i=0;i<=n;i++)
{
    for(j=0;j<=n;j++)
    {
        cout<<dp[i][j]<<" ";
    }
    cout<<endl;
}

cout<<endl<<endl;

for(i=0;i<=n;i++)
{
    for(j=0;j<=n;j++)
    {
        cout<<dp_smoke[i][j]<<" ";
    }
    cout<<endl;
}


 /* for(i=0;i<n;i++)
  {
  for(j=)


  }
*/

return dp_smoke[1][n];


}


int main()
{
long long int n,i;
while(scanf("%lld",&n)==1)
{



//printf("give the no of matrices\n");

/*if()
    return 0;*/

//printf("give the row column matrix\n");

long long int arr[n+1];

arr[0]=0;

for(i=1;i<=n;i++)
 scanf("%lld",&arr[i]);

cout<<min_mul(arr,n)<<endl;

}
return 0;
}