problem :mixture problem
My program took :-
Time :0.01
Mem :2.2M
I think i have used less memory(i used only array of 100 * 100,while others have used 2 array of 100*100 and 1 array of 100).
Others code took less time than my code.
please help me to reduce time and memory
In this i have use only 1 matrix of 100 *100 for both smoke and color , unlike others who have used different matrix for each of them .
#include <stdlib.h>
#include <stdio.h>
int main()
{
int m[100][100],n,i,j,k,q,l;
while(scanf("%d",&n)!=EOF) {
for(i = 0;i < n;i++) scanf("%d",&m[i][i]); // taking inputs in principal diagonal
if(n==1) {
printf ("%d\n",0);
continue;
}
for(i = 0;i < n-1;i++) {
j = i+1;
m[i][j] = (m[j][j] * m[i][i]) ; //color in lower side of principal diagonal (when only 2 mixtures are mixed)
m[j][i] = (m[j][j] + m[i][i])% 100; //smoke in upper side of principal diagonal (when only 2 mixtures are mixed)
}
for(l = 3;l <= n;l++) { //l = no of adjacent mixtures taken
for( i = 0;i <= n-l;i++) {
j = i+l-1;
k = i; //when mixing ith colour with other mixed l-1 colours
m[i][j] = m[k+1][j] + m[k][k]*m[j][k+1];
for(k = i+1 ;k < j-1;k++) {
q = m[i][k]+m[k+1][j] + m[k][i]*m[j][k+1];
if(q < m[i][j]) m[i][j] = q;
}
k = j - 1; //when mixing jth color with l-1 mixed color
q = m[i][k] + m[k][i] * m[j][j];
if(q < m[i][j]) m[i][j] = q;
m[j][i] = (m[j][j] + m[j-1][i])%100;
}
}
printf ("%d\n",m[0][n-1]);
}
return 0;
}