Paths through the Hourglass
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
#include <stdio.h>
#include <string.h> int n,s;
long long dp[][][];
int a[][]; int d(int x,int y,int m)
{
if(x>=*n-)
return ;
int v=a[x][y];
if(dp[x+][y][m-v]>)
{
printf("L");
d(x+,y,m-v);
}
else
{
printf("R");
d(x+,y+,m-v);
}
return ;
} int main()
{
int i,j,k;
while(scanf("%d %d",&n,&s)!=EOF)
{
if(n== && s==)
break;
memset(dp,,sizeof(dp));
for(i=;i<=n;i++)
{
for(j=i;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=n+;i<=*n-;i++)
{
for(j=n;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
} for(i=n;i<=*n-;i++)
{
int v=a[*n-][i];
dp[*n-][i][v]=;
}
for(i=n*-;i>n;i--)
{
for(j=n;j<=i;j++)
{
int v=a[i][j];
for(k=v;k<=s;k++)
{
dp[i][j][k]=dp[i+][j][k-v]+dp[i+][j+][k-v];
}
}
}
for(i=n;i>=;i--)
{
for(j=i;j<=n;j++)
{
int v=a[i][j];
for(k=v;k<=s;k++)
{
dp[i][j][k]=dp[i+][j][k-v]+dp[i+][j+][k-v];
}
}
} long long cnt=;
for(i=;i<=n;i++)
{
cnt=cnt+dp[][i][s];
}
printf("%lld\n",cnt);
for(i=;i<=n;i++)
{
if(dp[][i][s]>)
{
printf("%d ",i-);
d(,i,s);
break;
}
}
printf("\n");
}
return ;
}