CSES - Datatähti 2023 alku - Results
Submission details
Task:Ruudukko
Sender:Sup
Submission time:2022-11-09 15:39:32 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.37 s1, 2, 3details
#20.37 s1, 2, 3details
#30.37 s1, 2, 3details
#40.37 s2, 3details
#50.37 s2, 3details
#60.37 s2, 3details
#70.38 s3details
#80.37 s3details
#90.37 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:94:9: warning: unused variable 'index' [-Wunused-variable]
   94 |     int index;
      |         ^~~~~
input/code.cpp:95:9: warning: unused variable 'i' [-Wunused-variable]
   95 |     int i = 1;
      |         ^
input/code.cpp:96:9: warning: unused variable 'ii' [-Wunused-variable]
   96 |     int ii = 0;
      |         ^~
input/code.cpp:97:9: warning: unused variable 'iii' [-Wunused-variable]
   97 |     int iii = 0;
      |         ^~~
input/code.cpp:98:9: warning: unused variable 'n' [-Wunused-variable]
   98 |     int n = 3;
      |         ^

Code

// CPP program to count number
// of decreasing path in a matrix
//#include <bits/stdc++.h>
// using namespace std;
//#include <iostream>


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

#define MAX 1000000

// Function that returns the number of
// decreasing paths from a cell(i, j)
int CountDecreasingPathsCell(int mat[MAX][MAX], int dp[MAX][MAX],
                                              int n, int x, int y)
{
    // checking if already calculated
    if (dp[x][y] != -1)
        return dp[x][y];
 
    // all possible paths
    //int delta[4][2] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    int delta[4*n][2];
    int C = 0;
    for (int i = -n; i<=n; i++){
        if(i != 0){
            C++;
            delta[C][0] = i;
            delta[C][1] = 0;
        }
    }
    for (int i = -n; i<=n; i++){
        if(i != 0){
            C++;
            delta[C][0] = 0;
            delta[C][1] = i;
        }
    }
    
    
    int newx, newy;
 
    // counts the total number of paths
    int ans = 1;
 
    // In all four allowed direction.
    for (int i = 0; i < 4*n; i++) {
 
        // new co-ordinates
        newx = x + delta[i][0];
        newy = y + delta[i][1];
 
        // Checking if not going out of matrix and next
        // cell value is less than current cell value.
        if (newx >= 0 && newx < n && newy >= 0
            && newy < n && mat[newx][newy] < mat[x][y]) {
            ans += CountDecreasingPathsCell(mat, dp, n, newx, newy);
        }
    }
    // function that returns the answer
    return dp[x][y] = ans;
}
 
// Function that counts the total
// decreasing path in the matrix
int countDecreasingPathsMatrix(int n,
                               int mat[MAX][MAX])
{
    int dp[MAX][MAX];
 
    // Initialising dp[][] to -1.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = -1;
 
    int sum = 0;
 
    // Calculating number of decreasing path from each cell.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum += CountDecreasingPathsCell(mat, dp, n, i, j);
 
    return sum;
}





// Driver Code
int main()
{
    int index;
    int i = 1;
    int ii = 0;
    int iii = 0;
    int n = 3;
    int number_of_rows;
    cin >> number_of_rows; 
    int input_row[number_of_rows] = {};
    int input_row1;
    //string replace_char = ",";


    //int mat[1000][1000];

    int my_array[MAX][MAX];

    //cout << number_of_rows << endl;

    for (int iii = 0; iii < number_of_rows; iii++)
    {
        for (int ii = 0; ii < number_of_rows; ii++)
        {
            cin >> input_row1;

            input_row[ii] = input_row1;
            //cout << input_row1 << "its the input row" << endl;

            my_array[iii][ii] = input_row1;

            //char *modified_input = strtok(input_row, " ");
            //cout << modified_input << "its modified_input" << endl;
            //int number = stoi(modified_input);
            //cout << number << "its the number" << endl;
            //my_array[ii] = number;
            //cout << ii << "its the ii number" << endl;
            //cout << iii << "its the iii number----" << endl;

        }

        //my_array[iii] = input_row;
    }



    //int arrSize = sizeof(my_array)/sizeof(my_array[0]);
    //cout << arrSize << "its the length of arrSize" << endl;
    //cout << input_row[0] << "its the input_row---" << endl;
    //cout << input_row[1] << "its the input_row---" << endl;
    //cout << input_row[2] << "its the input_row---" << endl;

    //cout << my_array[0][0] << "its the my_array " << endl;
    //cout << my_array[1][1] << "its the my_array " << endl;

    //std::copy_n(std::istream_iterator<int>(std::cin), number_of_rows, my_array);

    //int mat[100][100] = { { 2, 1, 3 }, { 1, 1, 1 }, {9, 2, 7} };     // function call that returns the

    //cout << mat[50][0] << "its the mat print" << endl;
    cout << countDecreasingPathsMatrix(number_of_rows, my_array) << endl;      // count of decreasing paths in a matrix
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
3
1 1 1
1 1 1
1 1 1

correct output
9

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict:

input
3
1 2 3
6 5 4
7 8 9

correct output
135

user output
(empty)

Test 3

Group: 1, 2, 3

Verdict:

input
3
7 8 1
4 5 4
3 9 6

correct output
57

user output
(empty)

Test 4

Group: 2, 3

Verdict:

input
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
10000

user output
(empty)

Test 5

Group: 2, 3

Verdict:

input
100
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
187458477

user output
(empty)

Test 6

Group: 2, 3

Verdict:

input
100
2995 8734 1018 2513 7971 5063 ...

correct output
964692694

user output
(empty)

Test 7

Group: 3

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1000000

user output
(empty)

Test 8

Group: 3

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
229147081

user output
(empty)

Test 9

Group: 3

Verdict:

input
1000
520283 805991 492643 75254 527...

correct output
951147313

user output
(empty)