Ruudukko

#include "bits/stdc++.h"
#define int long long

using namespace std;

void init_code() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
} 


const int mod = 1e9+ 7;

map<int, int> mp;
int f (int i, int j, int n, vector<vector<int>>& g) {
  int sum = 0;

  if (mp[i * n + j]) {
    return mp[i * n + j];
  }
  
  if (g[i][j] == 1) {
    return 1;
  }

  for (int t = 0; t < n; ++t) {
    if (g[i][j] > g[i][t]) {
      if (g[i][t] == 1) {
        sum++;
      } else {
        sum += (f(i, t, n, g) + 1) % mod;
      }
    }
    if (g[i][j] >  g[t][j]) {
      if (g[t][j] == 1) {
        sum++;
      } else {
        sum += (f(t, j, n, g) + 1) % mod;
      }
    }
  }
  mp[i * n + j] += sum % mod;

  return sum % mod;
}

void solve() {
  int n;
  cin >> n;

  vector<vector<int>> g(n, vector<int> (n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> g[i][j];
    }
  } 
  
  int res = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (g[i][j] == 1) {
        res++;
        continue;
      }
      res += (f(i, j, n, g) + 1) % mod;
    }
  }
  
  res %= mod;
  cout << res << ' ';
}

signed main() {
  init_code();
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();  
  }
  return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED