Ruudukko

#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using namespace std;
 
using ll = long long;
 
int n;
set<pair<int,int>> allNumbers = set<pair<int,int>>();
map<int, set<pair<int, int>>> neighbours;
map<int, ll> counts;
 
void countPaths(pair<int,int> x) {
    if (counts.count(x.second)) {return;}
 
    counts[x.second] = 1;
    // same row
    for (auto y : neighbours[x.second / n + 1]) {
        if (y.first >= x.first) {break;}
        if (!counts.count(y.second))
            countPaths(y);
        counts[x.second] += counts[y.second];
        counts[x.second] %= 1000000007;
    }
    // same col
    for (auto y : neighbours[- (x.second % n) - 1]) {
        if (y.first >= x.first) {break;}
        if (!counts.count(y.second))
            countPaths(y);
        counts[x.second] += counts[y.second] ;
        counts[x.second] %= 1000000007;
    }
}
 
 
int main() {
    cin >> n;
 
    for (int i=1; i<n+1; i++) {
        neighbours[i] = set<pair<int,int>>();
        neighbours[-i] = set<pair<int,int>>();
    }
    int k;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> k;
            allNumbers.insert({k, n*i+j});
            neighbours[i+1].insert({k, n*i+j});
            neighbours[-j-1].insert({k, n*i+j});
        }
    }
    for (auto it = allNumbers.rbegin(); it != allNumbers.rend(); it++) {
        countPaths(*it);
    }
    ll total = 0;
    for (auto x : counts) {
        total += x.second;
        total %= 1000000007;
    }
 
    cout << total;
}

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