bzoj 5085: 最大——结论题qwq

Description

给你一个n×m的矩形，要你找一个子矩形，价值为左上角左下角右上角右下角这四个数的最小值，要你最大化矩形

的价值。

Input

第一行两个数n,m,接下来n行每行m个数，用来描述矩形

n, m ≤ 1000

Output

输出一个数表示答案

Sample Input

2 2
1 2
3 4

Sample Output

———————————————————————————

这道题ljk猜了个结论答案一定在那最大的4*n个点中所以用一下STL的nth_element

然后枚举一下对角线复杂度n^2就可以辣23333

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using std::swap;

using std::min;

using std::max;

const int M=2e3+;

char buf[M*M*],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

int n,m,k,s[M][M],cnt,sum,ans;

struct pos{

    int x,y,w;

    bool operator <(const pos& h)const{return w>h.w;}

}q[M*M];

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=read(); m=read(); k=std::min(*n,n*m);

    for(int i=;i<n;i++) for(int j=;j<m;j++)

    s[i][j]=read(),q[cnt++]=(pos){i,j,s[i][j]};

    std::nth_element(q,q+k,q+cnt);

    for(int i=;i<k;i++){

        for(int j=;j<i;j++)if(q[i].x!=q[j].x&&q[i].y!=q[j].y){

            sum=min(s[q[i].x][q[i].y],s[q[j].x][q[j].y]);

            sum=min(sum,s[q[i].x][q[j].y]);

            sum=min(sum,s[q[j].x][q[i].y]);

            ans=max(ans,sum);

        }

    }printf("%d\n",ans);

    return ;

}

秒客网