Ruudukko

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N =1e5;
const int inf = 1e9;
const ll mod = 1e9 + 7;

map<int, vector<pair<int, int>>> m;


int main(){

    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int> (n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
            m[a[i][j]].push_back({i, j});
        }
    }
    vector<vector<ll>> ans(n, vector<ll> (n));
    vector<vector<int>> cols(n), rows(n);
    for(int i = 1; i <= n * n; ++i){
        for(auto [y, x] : m[i]){
            ans[y][x] = 1;
            for(int y2 : cols[x]){
                if(y==0 && x==2){
                    // cout << y2 << "\n";
                }
                ans[y][x] += ans[y2][x];
                ans[y][x] %= mod;
            }
            for(int x2 : rows[y]){
                if(y==0 && x==2){
                    // cout << x2 << "\n";
                }
                ans[y][x] += ans[y][x2];
                ans[y][x] %= mod;
            }
        }

        for(auto [y, x] : m[i]){
            cols[x].push_back(y);
            rows[y].push_back(x);
        }
    }    

    ll sum = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            // cout << ans[i][j] << " ";
            sum += ans[i][j];
            sum%=mod;
        }
        // cout << "\n";
    }

    cout << sum << "\n";



    
}

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: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED