Ruudukko

input/code.cpp: In function 'uint64_t laske_reitit(int, int)':
input/code.cpp:23:22: warning: comparison of integer expressions of different signedness: 'uint64_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     if (reitit[i][j] != -1) {
      |         ~~~~~~~~~~~~~^~~~~
input/code.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'uint64_t' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (cols[i][k].first >= ruudukko[i][j]) {
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
input/code.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'uint64_t' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (rows[j][k].first >= ruudukko[i][j]) {
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>

using namespace std;

int n;
uint64_t reitit[1000][1000];
uint64_t ruudukko[1000][1000];
pair<int, pair<int, int>> rows[1000][1000];
pair<int, pair<int, int>> cols[1000][1000];

uint64_t maaralaske_reitit = 0;
uint64_t maaralaske_reitit_nopea = 0;

bool rowcolcmp(pair<int, pair<int, int>> i, pair<int, pair<int, int>> j)
{
    return i.first < j.first;
}

uint64_t laske_reitit(int i, int j)
{
    //cout << "laske_reitit " << i << " " << j << endl;

    if (reitit[i][j] != -1) {
        //maaralaske_reitit_nopea++;
        return reitit[i][j];
    }

    uint64_t nreitit = 0;

    for (int k = 0; k < n; k++) {
        //cout << "col " << cols[i][k].first << ": " << cols[i][k].second.first << ", " << cols[i][k].second.second << endl;
        //cout << "comp " << ruudukko[i][j] << endl;
        if (cols[i][k].first >= ruudukko[i][j]) {
            break;
        }

        nreitit += 1 + laske_reitit(i, cols[i][k].second.second);
    }

    for (int k = 0; k < n; k++) {
        //cout << "row " << rows[j][k].first << ": " << rows[j][k].second.first << ", " << rows[j][k].second.second << endl;
        //cout << "comp " << ruudukko[i][j] << endl;
        if (rows[j][k].first >= ruudukko[i][j]) {
            break;
        }

        nreitit += 1 + laske_reitit(rows[j][k].second.first, j);
    }

    /*for (int k = 0; k < n; k++) {
        maaralaske_reitit++;
        if (ruudukko[i][k] < ruudukko[i][j]) {
            nreitit += 1 + laske_reitit(i, k);
        }

        if (ruudukko[k][j] < ruudukko[i][j]) {
            nreitit += 1 + laske_reitit(k, j);
        }
    }*/

    reitit[i][j] = nreitit;
    return nreitit;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> ruudukko[i][j];
            rows[j][i] = make_pair(ruudukko[i][j], make_pair(i, j));
            cols[i][j] = make_pair(ruudukko[i][j], make_pair(i, j));
            reitit[i][j] = -1;
        }
    }

    for (int i = 0; i < n; i++) {
        sort(rows[i], rows[i]+n, rowcolcmp);
        sort(cols[i], cols[i]+n, rowcolcmp);
    }

    uint64_t nreitit = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            nreitit += 1 + laske_reitit(i, j);
        }
    }

    cout << nreitit % 1000000007 << endl;
    //cout << "Määrä laske_reitit: " << maaralaske_reitit << endl;
    //cout << "Määrä laske_reitit nopea: " << maaralaske_reitit_nopea << endl;
}

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

Test 6

Group: 2, 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED