Ruudukko

#include <bits/stdc++.h>
 
typedef long long ll;
 
#define M 1000000007
#define N (1 << 18)
 
using namespace std;
 
ll ways[1001][1001];
int v[1001][1001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, pair<int, int>>> ord;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> v[i][j]; 
            ord.push_back({v[i][j], {i, j}});
            ways[i][j] = 1;
        }
    }
 
    sort(ord.rbegin(), ord.rend());
 
    ll ans = 0;
 
    for (auto [a, b] : ord) {
        auto [i, j] = b;
 
        for (int k = 0; k < n; ++k) {
            if (v[k][j] < a) {
                ways[k][j] = (ways[k][j] + ways[i][j]) % M;
            }
            if (v[i][k] < a) {
                ways[i][k] = (ways[i][k] + ways[i][j]) % M;
            }
        }
 
        ans += ways[i][j];
        ans %= M;
    }
 
    cout << ans << "\n";
 
    return 0;
}

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