Ruudukko

#include <bits/stdc++.h>
using namespace std;

#define MAX    1000
#define MODULO 1000000007

int input_array[MAX][MAX]; // this is the input array
long result_array[MAX][MAX]; // this holds the final path counts in each cell
bool compute_array[MAX][MAX]; // this tracks which cells were computed

// Function that computes number of paths
// starting from cell (x,y)
long ComputeCellPaths(int n, int x, int y)
{
    // checking if already calculated
    if (compute_array[x][y]) {
         return result_array[x][y];
   }

    long pathCount = result_array[x][y];
    for (int i = 0; i < n; i++) {
        if (input_array[i][y] < input_array[x][y]) {
            pathCount = pathCount + 1 + ComputeCellPaths(n, i, y);
        }
        if (input_array[x][i] < input_array[x][y]) {
            pathCount = pathCount + 1 + ComputeCellPaths(n, x, i);
        }
    }
    result_array[x][y] = pathCount % MODULO;
    compute_array[x][y] = true;

    return pathCount;
}


// Main function
int main()
{
    //int i = 1;
    int number_of_rows;

    // Input read
    cin >> number_of_rows; 
    for (int i = 0; i < number_of_rows; i++)
    {
        for (int j = 0; j < number_of_rows; j++)
        {
            int input_row;

            cin >> input_row;
            input_array[i][j] = input_row;
            result_array[i][j] = 0;
            if (input_row == 1) {
                compute_array[i][j] = true;    
            } else {
                compute_array[i][j] = false;
            }
        }
    }

    // Calculating number of paths from each cell
    long numberOfPaths = number_of_rows * number_of_rows; // we count separately the "own" reference
    for (int i = 0; i < number_of_rows; i++){
        for (int j = 0; j < number_of_rows; j++){
            numberOfPaths = numberOfPaths + ComputeCellPaths(number_of_rows, i, j);
        }
    }

    cout << (numberOfPaths%MODULO) << endl;      // count of decreasing paths in a matrix
    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