Ruudukko

#include <bits/stdc++.h>

using namespace std;


int grid[1000][1000], steps[1000][1000];
long long getRoutes(int x, int y,int n){

	if(steps[x][y]!=-1){
		return steps[x][y];
	}
	long long count = 0;
	for (int i=0;i<n;i++){
		if(grid[i][y]<grid[x][y]){
			count += getRoutes(i,y,n)+1;
			count = count%1000000007;
		}
	}
	for (int i=0;i<n;i++){
		if(grid[x][i]<grid[x][y]){
			count += getRoutes(x,i,n)+1;
			count = count%1000000007;
		}
	}
	steps[x][y]=count;
	return count%1000000007;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>grid[j][i];
			steps[j][i]=-1;
		}
	}
	long long routes=0;
	for (int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			routes += getRoutes(j,i,n)+1;
			routes = routes%1000000007;
		}
	}
	cout<<routes<<"\n";
}

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: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED