Sword Of The Morning, a pretty badass name as it sounds relates to a character in Game Of Thrones, Sir Arthur Dayne, regarded as the most skillfull swordsman in the history of Westeros.

If the constraints are small like the matrix is 20 by 20 we can use dp + bit masking. Refer to this problem to gain some idea about dp + bit masking. https://www.spoj.com/problems/ASSIGN/

Here is the code:

int n;
int memo[1<<20][20];
int matrix[20][20];
int dp(int mask, int i)
{
  if(memo[mask][i] != -1)
        return memo[mask][i];

  int ans = 0;
  for(int j = 0; j < n; j++)
    if( !(mask&(1<<j)) )//not set
        ans = max(ans, matrix[i][j] + dp(mask|(1<<j), i+1));
  return memo[mask][i] = ans;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> matrix[i][j];
    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            memo[i][j] = -1;
    cout << dp(0, 0);
}

Auto comment: topic has been updated by Aafat_Wapas (previous revision, new revision, compare).

Thanks :)

Can you please explain how you arrived at this approach.

Auto comment: topic has been updated by Aafat_Wapas (previous revision, new revision, compare).

Thanks for the explanation :)

UPD3: Contest has been delayed by 10 mins :)