题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
const int maxm = 1100;
typedef long long ll;
int n;
bool ok[maxn][maxm];
ll solve(){
    ll ans = 0;
    vector<int> lst(n, n - 1);
    vector<int> to_add[maxn];
    for(int i = n - 1; i >= 0; i--){
        for(int j = 1; j < n; j++){
            to_add[j].clear();
        }
        for(int k = 0; k < n; k++){
            if(ok[i][k] == 0){
                lst[k] = i - 1;
            }else{
                to_add[lst[k]].push_back(k);
            }
        }
        int sum_comb = 0;
        vector<int> lef(n, -1), rig(n, -1);
        for(int j = n - 1; j >= i; j--){
            for(int k : to_add[j]){
                int l = k, r = k;
                auto c2 = [](int x){
                    return (x + 1) * (x + 2) / 2;
                };
                if(k and lef[k - 1] != -1){
                    l = lef[k - 1];
                    sum_comb -= c2(k - 1 - l);
                }
                if(k + 1 < n and rig[k + 1] != -1){
                    r = rig[k + 1];
                    sum_comb -= c2(r - k - 1);
                }
                lef[r] = l;
                rig[l] = r;
                sum_comb += c2(r - l);
            }
            ans += sum_comb;
        }
    }
    return ans;
}
int main(){
    cin >> n;
    vector<vector<int>> pasture(n, vector<int>(n));
    for(vector<int>& a : pasture){
        for(int& b : a){
            cin >> b;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ok[i][j] = pasture[i][j] >= 100;
        }
    }
    ll ans = solve();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ok[i][j] = pasture[i][j] > 100;
        }
    }
    ans -= solve();
    cout << ans << endl;
    return 0;
}