Ruudukko

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int mod = 1e9 + 7;

int main() {
    int n; cin >> n;
    vector<vector<int>> t(n, vector<int> (n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> t[i][j];
        }
    }

    vector<set<int>> pref(n * n);
    vector<vector<pair<int, int>>> helpi(n);
    vector<vector<pair<int, int>>> helpj(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            helpi[i].push_back({t[i][j], i * n + j});
            sort(helpi[i].begin(), helpi[i].end());
            reverse(helpi[i].begin(), helpi[i].end());
        }
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            helpj[j].push_back({t[i][j], i * n + j});
            sort(helpj[j].begin(), helpj[j].end());
            reverse(helpj[j].begin(), helpj[j].end());
        }
    }

    int s;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            s = 0;
            while (s < n && helpi[i][s].first > t[i][j]) {
                if (helpi[i][s].second != i * n + j) {
                    pref[i * n + j].insert(helpi[i][s].second);
                }
                s++;
            }
            s = 0;
            while (s < n && helpj[j][s].first > t[i][j]) {
                if (helpj[j][s].second != i * n + j) {
                    pref[i * n + j].insert(helpj[j][s].second);
                }
                s++;
            }
        }
    }

    vector<vector<int>> dp(n * n, vector<int> (n * n));
    for (int c = 1; c <= n * n; c++) {
        for (int i = 0; i < n * n; i++) {
            if (c == 1) {
                dp[c - 1][i] = 1;
            } else {
                dp[c - 1][i] = 0;
                for (auto naa : pref[i]) {
                    dp[c - 1][i] += dp[c - 2][naa];
                    dp[c - 1][i] %= mod;
                }
            }
        }
    }
    int ANS = 0;
    for (int c = 1; c <= n * n; c++) {
        for (int i = 0; i < n * n; i++) {
            ANS += dp[c - 1][i];
            ANS %= mod;
        }
    }
    cout << ANS;
}

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

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED