Ruudukko

#include <iostream>
int n;
int visited = 0;
int sum = 0;
int arr[1001][1001];
int gps[1001][1001]={0};
int gps2[3][1001];

int route(int x, int y){
    if (gps[x][y]!=0)
        return gps[x][y];
    int gpsdie = (gps2[0][y]<gps2[1][x]) ? gps2[0][y] : gps2[1][x];
    if (arr[x][y]==gpsdie){
        gps[x][y] = 1;
        visited++;
        sum++;
        return 1;
    }
    int routes = 1;
    for (int i=0;i<n;i++){
        if (y!=i){
        if (arr[x][i]<arr[x][y])
            routes += route(x,i);
        //if (routes>1000000007)
            routes %= 1000000007;
        }
        if (x!=i){
        if (arr[i][y]<arr[x][y])
            routes += route(i,y);
        //if (routes>1000000007)
            routes %= 1000000007;
        }
    }
    gps[x][y] = routes;
    visited++;
    sum += routes;
    if (sum>=1000000007)
        sum %= 1000000007;
    return routes;
}

int main(){
    std::cin.sync_with_stdio(false);
    std::cin >> n;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            std::cin >> arr[i][j];
        }
    }
    int xd = n*n;
    int small = 1000001;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (arr[j][i]<small)
                small = arr[j][i];
        }
        gps2[0][i] = small;
        small = 1000001;
        for (int j=0;j<n;j++){
            if (arr[i][j]<small)
                small = arr[i][j];
        }
        gps2[1][i] = small;
        small = 1000001;
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            route(i,j);
            if (visited==xd)
                goto results;
        }
    }
    results:
    std::cout << sum << "\n";
    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