MIXTURES getting TLE! Why?

I tried solving the problem using bottom up dp. But I ended up with TLE’s. How do I optimise the code to get AC?

 #include<cstdio>
using namespace std;

int main()
{
    while(1)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            m[i][i]=0;
            c[i][i]=a[i];
        }
        for(int l=2;l<=n;l++)
        {
            for(int i=0;i<=n-l;i++)
            {
                int j = i+l-1;
                m[i][j]=9999;
                for(int k=i;k<=j-1;k++)
                {
                    int q = m[i][k]+m[k+1][j]+c[i][k]*c[k+1][j];
                    if(q<m[i][j])
                    {
                        m[i][j]=q;
                        c[i][j] = (c[i][k]+c[k+1][j])%100;
                    }
                }
            }
        }
        printf("%d\n",m[0][n-1]);
    }
    return 0;
}

I also tried placing while(scanf("%d",&n)!=EOF)). This gives correct answers for the sample input but I get WA on codechef. Why? Where am I wrong?

1 Like
//