Ruudukko

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

// Main function
int main()
{
    int number_of_rows;//This will keep the size of the input matrix
    int curentValue;//This will keep the value of the curent matrix element which is processed (see the for loops where the distances are calculated)
    long numberOfPaths = 0;//This will keep the final number of paths
    int maximumValue = 0;//This is will keep the maximum value of the elements of the input matrix. We need this so that if maximumValue < N*N we do not iterate over maximumValue. To save some useless iterations
    // Input read
    cin >> number_of_rows;
    int M = number_of_rows * number_of_rows;//This is the maximum number of distinct values which can be in the input matrix
    int minimumValue = M;//This will contain the minimum value of the elements of the input matrix. This is usefull so that we do not test for values 1...minimumValue since we know they are not in the input matrix
    int** input_array = new int* [number_of_rows];//This is the 2D array which keeps the input matrix
    //We created dynamically the input matrix based on the input size
    for (int i = 0; i < number_of_rows; i++) {
        input_array[i] = new int[number_of_rows];
    }
    //***************************************************************
    long** result_array = new long* [number_of_rows];//This is the 2D array which keeps the number of paths for each element of the input matrix
    //We created dynamically the result matrix based on the input size
    for (int i = 0; i < number_of_rows; i++) {
        result_array[i] = new long[number_of_rows];
    }
    //****************************************************************
    int* a = new int [number_of_rows* number_of_rows + 1]{0};//This is the 1D array which keeps only the distinct elements from the input array. Initialized with zeros. We create it dinamically
    //Here we read the matrix from the input and initialize the arrays
    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] = 1;
            a[input_row] = input_row;
            if (input_row > maximumValue) {
                maximumValue = input_row;
            }
            if (input_row < minimumValue) {
                minimumValue = input_row;
            }
        }
    }
    //****************************************************************
    for (int index = minimumValue; index <= maximumValue; index++) {//Here we loop over the values of the elements of the matrix (from minimum to the maximum) and we propagate their distances to the coresponding elements which have larger values
        curentValue = a[index];
//        if (curentValue == maximumValue) {//If the curent value is the maximum value we do nothing since it was taken care of
//            break;
//        }
        if (curentValue > 0) {//If we have an existing input value we calculate the distances. If this is zero it means that the value, equal to the index, is not present into the input matrix
            for (int x = 0; x < number_of_rows; x++) {//We loop over the matrix columns
                for (int y = 0; y < number_of_rows; y++) {//we loop over the matrix rows
                    if (input_array[y][x] == curentValue) {//If we found a value equal to the curent value, it means we have calculated its distances and we propagate them to the larger values which are on same line and same colomn
                        for (int vertDir = 0; vertDir < number_of_rows; vertDir++) {//We go on same loop over both, the vertical and horizontal lines
                            if (input_array[vertDir][x] > curentValue) {
                                result_array[vertDir][x] = (result_array[vertDir][x] + result_array[y][x]) % 1000000007;
                            }
                            if (input_array[y][vertDir] > curentValue) {
                                result_array[y][vertDir] = (result_array[y][vertDir] + result_array[y][x]) % 1000000007;
                            }
                        }
                    }
                }
            }
        }
    }
    //We go a final loop over the matrix of the distances and calculate the final sum of distances
    for (int x = 0; x < number_of_rows; x++) {
        for (int y = 0; y < number_of_rows; y++) {
            numberOfPaths = (numberOfPaths + result_array[y][x]) % 1000000007;
        }
    }
    //********************************************************************************************
    //Now clean the memory (due to dynamic allocation of some arrays)
    delete [] a;
    for (int i = 0; i < number_of_rows; i++) {
        delete [] input_array[i];
    }
    delete [] input_array;
    for (int i = 0; i < number_of_rows; i++) {
        delete [] result_array[i];
    }
    delete [] result_array;
    //***************************************************************
    cout << (numberOfPaths) << endl;      // Print at console the final number of paths
    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: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED