Ruudukko

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

using namespace std;

const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<int> t(n * n);
    vector<pair<int, int>> a(n * n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> t[i * n + j];
            a[i * n + j] = {t[i * n + j], i * n + j};
        }
    }
    sort(a.begin(), a.end());

    vector<int> dp(n * n, 0);
    vector<vector<int>> ii(n);
    vector<vector<int>> jj(n);

    int ANS = 0;

    for (int x = 0; x < n * n; x++) {
        int now = a[x].second;
        int inow = now / n;
        int jnow = now % n;

        int isize = ii[inow].size();
        for (int p = 0; p < isize; p++) {
            if (t[now] > t[ii[inow][p]]) {
                dp[now] += dp[ii[inow][p]];
                dp[now] %= mod;
            }
        }
        ii[inow].push_back(now);

        int jsize = jj[jnow].size();
        for (int p = 0; p < jsize; p++) {
            if (t[now] > t[jj[jnow][p]]) {
                dp[now] += dp[jj[jnow][p]];
                dp[now] %= mod;
            }
        }
        jj[jnow].push_back(now);

        dp[now] += 1;
        ANS += dp[now];
        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: 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