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?