I have been working on the [SUMTRAIN][1] problem. I used the approach mentioned [here][2]. Following is the code that I have come up with.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,a,b,e,f,g;
cin>>t;
while(t--)
{
cin>>n;
int arr[n][n];
for(a=0;a<n;a++)
for(b=0;b<=a;b++)
cin>>arr[a][b];
if(n==1)
cout<<arr[0][0]<<endl;
else if(n==2)
{
if(arr[1][0]>arr[1][1])
cout<<arr[0][0]+arr[1][0]<<endl;
else
cout<<arr[0][0]+arr[1][1]<<endl;
}
else
{
while(n--)
{
int d[(n-1)*2];
for(e=0;e<((n-1)*2);e++)
{
d[e]=arr[n-1][f]+arr[n-2][e-f];
if(e%2==0)
f++;
}
sort(d,d+(sizeof(d)/sizeof(int)));
reverse(d,d+(sizeof(d)/sizeof(int)));
for(g=0;g<(n-1);g++)
arr[n-2][g]=d[g];
cout<<arr[0][0]<<endl;
}
}
}
return 0;
}
I am not getting solutions for any n>2. What could be the problem?
[1]: http://www.codechef.com/problems/SUMTRIAN/
[2]: http://discuss.codechef.com/questions/4557/need-guidance-in-sums-in-triangle-problem