Ruudukko

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

ll ways[1001][1001];
ll rowsum[1001];
ll colsum[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;

    ll bef = 1e9;

    vector<pair<int, int>> rowadd;
    vector<pair<int, int>> coladd;

    for (auto [a, b] : ord) {
        auto [i, j] = b;

        if (a < bef) {
            for (auto [idx, val] : rowadd) {
                rowsum[idx] += val;
                rowsum[idx] %= M;
            }
            for (auto [idx, val] : coladd) {
                colsum[idx] += val;
                colsum[idx] %= M;
            }
            rowadd.clear();
            coladd.clear();
            bef = a;
        }

        ways[i][j] = (1 + rowsum[i] + colsum[j]) % M;

        coladd.push_back({j, ways[i][j]});
        rowadd.push_back({i, ways[i][j]});

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

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED