求第k大用堆维护最值并出堆的时候扩展的经典题...
因为只有正数，所以一个矩阵的权值肯定比它的任意子矩阵的权值大，那么一开始把所有满足条件的最小矩阵加进堆里，弹出的时候上下左右扩展一行加进堆，用hash判重即可
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<queue> #define uint unsigned int #define ull unsigned long long using namespace std; const int maxn=1010, mod=10000019; struct poi{int x1, yy1, x2, y2; uint sum;}; struct tjm{ull too; int pre;}e[2000010]; priority_queue<poi>q; bool operator<(poi a, poi b){return a.sum>b.sum;} int n, m, mna, mnb, k, tot; int last[mod]; uint mp[maxn][maxn]; void read(uint &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, ull y){e[++tot].too=y; e[tot].pre=last[x]; last[x]=tot;} inline int makehs(ull x) { int tmp=x%mod; for(int i=last[tmp];i;i=e[i].pre) if(e[i].too==x) return i; add(tmp, x); return tot; } inline int hs(ull x) { int tmp=x%mod; for(int i=last[tmp];i;i=e[i].pre) if(e[i].too==x) return i; return -1; } inline void update(int x1, int yy1, int x2, int y2) { ull tmp=0; tmp=tmp*2333+x1; tmp=tmp*2333+yy1; tmp=tmp*2333+x2; tmp=tmp*2333+y2; if(hs(tmp)!=-1) return; makehs(tmp); q.push((poi){x1, yy1, x2, y2, mp[x2][y2]-mp[x2][yy1-1]-mp[x1-1][y2]+mp[x1-1][yy1-1]}); } int main() { scanf("%d%d%d%d%d", &n, &m, &mna, &mnb, &k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]), mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1]; for(int i=mna;i<=n;i++) for(int j=mnb;j<=m;j++) { ull tmp=0; int x1=i-mna+1, yy1=j-mnb+1, x2=i, y2=j; tmp=tmp*2333+x1; tmp=tmp*2333+yy1; tmp=tmp*2333+x2; tmp=tmp*2333+y2; makehs(tmp); q.push((poi){x1, yy1, x2, y2, mp[x2][y2]-mp[x2][yy1-1]-mp[x1-1][y2]+mp[x1-1][yy1-1]}); } for(int i=1;i<=k;i++) { if(q.empty()) return puts("-1"), 0; poi t=q.top(); q.pop(); int x1=t.x1, yy1=t.yy1, x2=t.x2, y2=t.y2; if(x1>1) update(x1-1, yy1, x2, y2); if(yy1>1) update(x1, yy1-1, x2, y2); if(x2<n) update(x1, yy1, x2+1, y2); if(y2<m) update(x1, yy1, x2, y2+1); if(i==k) printf("%u ", t.sum); } }