75pts:
可以暴力。
时间复杂度\(O(n^2m^2k)\)
175pts:
运用二维前缀和的思想即可。
时间复杂度\(O(mnk)\)
300pts:
我们实际是在维护一些一次函数，对于各个点 \(x\) 快速求出\(max_{f_i(x)}\)
而最后能产生贡献的，即处在最上方的那些线段，一定是一个凸包的形状。

所以，我们按照各个一次函数的斜率\(k\)排序，维护这个凸包即可。
时间复杂度是\(O((nm)\log (nm) + k)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll a[2005][2005], b[2005][2005], pref_a[2005][2005], pref_b[2005][2005], ans[1000005];
int n,m,r,c,t;
const ll maxt = 1e6+10;
ll f(ll k, ll b, ll x){return k*x+b;}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>b[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 
    {
        pref_a[i][j] = pref_a[i-1][j] + pref_a[i][j-1] + a[i][j] - pref_a[i-1][j-1];
        pref_b[i][j] = pref_b[i-1][j] + pref_b[i][j-1] + b[i][j] - pref_b[i-1][j-1];
    }
    cin>>r>>c>>t;
    vector<pair<ll,ll>> linear_functions;
    for(int i=1;i<=n-r+1;i++) for(int j=1;j<=m-c+1;j++)
        linear_functions.push_back(make_pair(
            pref_b[i+r-1][j+c-1] + pref_b[i-1][j-1] - pref_b[i-1][j+c-1] - pref_b[i+r-1][j-1],
            pref_a[i+r-1][j+c-1] + pref_a[i-1][j-1] - pref_a[i-1][j+c-1] - pref_a[i+r-1][j-1]
            ));
    sort(linear_functions.begin(), linear_functions.end());
    vector<tuple<ll,ll,ll>> convex_hull; 
    convex_hull.push_back(make_tuple(0, linear_functions.begin()->first, linear_functions.begin()->second));
    linear_functions.erase(linear_functions.begin());
    for(auto it:linear_functions)
    {
        while(!convex_hull.empty())
        {
            ll index, k, b;
            tie(index, k, b) = convex_hull.back();
            if(f(k,b,t)>=f(it.first, it.second, t)) goto outer;
            if(f(k,b,index) <= f(it.first, it.second, index))
                convex_hull.pop_back();
            else break;
        }
        if(convex_hull.empty()) convex_hull.push_back(make_tuple(0, it.first, it.second));
        else convex_hull.push_back(make_tuple(max(0.0, ceil(
            (it.second - get<2>(convex_hull.back())) * 1.0 / (get<1>(convex_hull.back()) - it.first))
        ),it.first, it.second)); // k_1 x + b_1 = k_2 x + b_2
        outer:;
    }
    for(int i = 0; i < convex_hull.size(); i++)
    {
        int k = (i==convex_hull.size()-1 ? t : get<0>(convex_hull[i+1]));
        for(int j = get<0>(convex_hull[i]); j < k; j++)
            ans[j] = get<1>(convex_hull[i]) * j + get<2>(convex_hull[i]);
    }
    for(int i = 0; i < t; i++) cout<<ans[i]<<'\n';
    return 0;
}

顺便一提，本题是 "P4254[JSOI2008]Blue Mary开公司" 的简单版本。如果需要强制在线，可以采用Li-Chao Segment tree解决。