Hello, in this problem [1011 — Marriage Ceremonies](http://lightoj.com/volume_showproblem.php?problem=1011)the **priority index** is not clear to me. I used bottom up manner and calculate the max adjacent values. ↵
Like-↵
↵
~~~~~↵
3↵
↵
1 2 3↵
↵
6 5 4↵
↵
8 1 2↵
~~~~~↵
↵
for me the values are `8 6 2` total `16`.But the submission gets wa. In udebug one test case is-↵
↵
~~~~~↵
5↵
5 10 10 2 3↵
2 11 3 10 10↵
16 12 1 5 2↵
4 2 11 5 2↵
1 8 14 4 13↵
~~~~~↵
↵
Ans:60.Which for me `14 11 12 11 10` total `58`.What am I missing here? Need help with that.↵
↵
↵
<spoiler summary="My code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
const int N=2e6+5,mod=1e9+7;↵
↵
int mat[20][20],dp[20][20];↵
int main()↵
{↵
int t,cnt=1;cin>>t;↵
while(t--)↵
{↵
int n;cin>>n;↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
cin>>mat[i][j];↵
}↵
}↵
memset(dp,0,sizeof(dp));↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
if(n&1)↵
{↵
if(j==(n+1)/2)↵
{↵
int temp=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]);↵
dp[i][j]=max(dp[i][j],temp)+mat[i][j];↵
}↵
else if(j<(n+1)/2)↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];↵
}↵
else↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];↵
}↵
}↵
else↵
{↵
if(j<=n/2)↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];↵
}↵
else↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];↵
}↵
}↵
}↵
}↵
//cout<<endl;↵
int ma=0;↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
//cout<<dp[i][j]<<" ";↵
ma=max(ma,dp[i][j]);↵
}↵
//cout<<endl;↵
}↵
cout<<"Case "<<cnt++<<": "<<ma<<endl;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
~~~~~↵
3↵
↵
1 2 3↵
↵
6 5 4↵
↵
8 1 2↵
~~~~~↵
↵
for me the values are `8 6 2` total `16`.But the submission gets wa. In udebug one test case is-↵
↵
5↵
5 10 10 2 3↵
2 11 3 10 10↵
16 12 1 5 2↵
4 2 11 5 2↵
1 8 14 4 13↵
~~~~~↵
↵
Ans:60.Which for me `14 11 12 11 10` total `58`.What am I missing here? Need help with that.↵
↵
↵
<spoiler summary="My code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
const int N=2e6+5,mod=1e9+7;↵
↵
int mat[20][20],dp[20][20];↵
int main()↵
{↵
int t,cnt=1;cin>>t;↵
while(t--)↵
{↵
int n;cin>>n;↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
cin>>mat[i][j];↵
}↵
}↵
memset(dp,0,sizeof(dp));↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
if(n&1)↵
{↵
if(j==(n+1)/2)↵
{↵
int temp=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]);↵
dp[i][j]=max(dp[i][j],temp)+mat[i][j];↵
}↵
else if(j<(n+1)/2)↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];↵
}↵
else↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];↵
}↵
}↵
else↵
{↵
if(j<=n/2)↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];↵
}↵
else↵
{↵
dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];↵
}↵
}↵
}↵
}↵
//cout<<endl;↵
int ma=0;↵
for(int i=1;i<=n;++i)↵
{↵
for(int j=1;j<=n;++j)↵
{↵
//cout<<dp[i][j]<<" ";↵
ma=max(ma,dp[i][j]);↵
}↵
//cout<<endl;↵
}↵
cout<<"Case "<<cnt++<<": "<<ma<<endl;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
