Max Sum of Rectangle Report You are given a non-...

Below is an efficient C++ solution (uses prefix sums + ordered set).
Time complexity: $O(\min(M,N)^2 \cdot \max(M,N)\log \max(M,N))$.
It reads M N K, then the M×N matrix, and prints the maximum rectangle sum ≤ K.

cpp
#include <bits/stdc++.h>
using namespace std;

static long long maxSubarrayNoLargerThanK(const vector<long long>& arr, long long K) {
    long long best = LLONG_MIN;
    long long prefix = 0;
    multiset<long long> pref; // use ordered container for lower_bound
    pref.insert(0);           // empty prefix

    for (long long x : arr) {
        prefix += x;
        // Find smallest prev >= prefix - K  ==> prefix - prev <= K and as large as possible
        auto it = pref.lower_bound(prefix - K);
        if (it != pref.end()) {
            best = max(best, prefix - *it);
        }
        pref.insert(prefix);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, N;
    long long K;
    if (!(cin >> M >> N >> K)) return 0;

    vector<vector<long long>> A(M, vector<long long>(N));
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];

    // To optimize, iterate over the smaller dimension as columns.
    bool transposed = false;
    if (N > M) {
        // Transpose to make columns <= rows
        vector<vector<long long>> T(N, vector<long long>(M, 0));
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                T[j][i] = A[i][j];
        A.swap(T);
        swap(M, N); // now M >= N
        transposed = true; // not used further, but kept for clarity
    }

    long long answer = LLONG_MIN;

    // Fix left and right column boundaries and reduce to 1D problem on rows.
    for (int left = 0; left < N; ++left) {
        vector<long long> rowSums(M, 0);
        for (int right = left; right < N; ++right) {
            for (int r = 0; r < M; ++r) rowSums[r] += A[r][right];
            long long bestHere = maxSubarrayNoLargerThanK(rowSums, K);
            answer = max(answer, bestHere);
            if (answer == K) { // Can't do better than exactly K
                cout << answer << '\n';
                return 0;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

How it works (briefly):

• Fix a pair of columns [left, right], compress each row to the sum between these columns → a 1D array.
• For that 1D array, use prefix sums and a multiset to find the maximum subarray sum ≤ K.
• Repeat over all column pairs (choosing the smaller dimension for columns to keep it fast).