Ruudukko

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define fi first
#define se second
using ll = long long;
 
const int N = 1001, M = 1e9+7;
ll row[N], column[N];
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    vector<pair<int, pair<int, int>>> v;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            v.push_back({x, {i, j}});
        }
    }
    sort(all(v));
 
    ll ans = 0;
    int p = 0;
    stack<pair<ll, pair<int, int>>> st;
    for (auto u : v) {
 
        int x = u.fi;
        auto [i, j] = u.se;
 
        if (x != p) {
            while (!st.empty()) {
                auto k = st.top(); 
                st.pop();
                row[k.se.fi] += k.fi;
                column[k.se.se] += k.fi;
                if (row[k.se.fi] > M) row[k.se.fi] %= M;
                if (column[k.se.se] > M) column[k.se.se] %= M;
            }
            p = x;
        }
 
        st.push({row[i] + column[j] + 1, {i, j}});
 
        ans += row[i] + column[j] + 1;
        if (ans > M) 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