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