新breath

~~~
/*先分析复杂度，n^2*m^2 的复杂度明显超过1e8，所以想想二分/线段树/双指针解法，本题中先枚举n^2，非常小，先假设固定上下端点，再枚举列，判断每一列的最大最小值，然后运用线段树维护列区间最大值，最小值，所以 build(1,m,1),n^2*mlogm的复杂度，可以接受，这样就枚举行确定列的区间最大值与最小值，最后判断不能m^2，想想双指针与二分，右端点在下右移动的时候，左端点只能向右移动，反证法易得，所以找到第一个>x的值的r，它的答案 就是 min（r-1-l+1）*（u-d+1）枚举(u,d)
    */
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
const int mod = 998244353;
int a[101][maxn] , nowa[maxn] , nowi[maxn], n , m , k;
int ma[maxn *4],mi[maxn *4];
void build(int l , int r,int rt){
    if(l == r){
        ma[rt] = nowa[l];
        mi[rt] = nowi[l];
        return ;
    }
    int mid = (l + r) >>1;
    build(l , mid , rt << 1);
    build(mid + 1 , r , rt << 1 | 1);
    ma[rt] = max(ma[rt << 1] , ma[rt << 1 | 1]);
    mi[rt] = min(mi[rt << 1] , mi[rt << 1 | 1]);

}
int queryma(int L,int R,int l , int r,int rt){
    int res = 0;
    if(L <= l && R >= r){
        return ma[rt];
    }
    int mid = (l + r) / 2;
    if(L <= mid) res = max(res , queryma(L , R , l , mid , rt << 1));
    if(R > mid) res = max(res , queryma(L , R , mid + 1 , r , rt << 1 | 1));
    return res;
}
int querymi(int L,int R,int l , int r,int rt){
    int res = 1e9;
    if(L <= l && R >= r){
        return mi[rt];
    }
    int mid = (l + r) / 2;
    if(L <= mid) res = min(res , querymi(L , R , l , mid , rt << 1));
    if(R > mid) res = min(res , querymi(L , R , mid + 1 , r , rt << 1 | 1));
    return res;
}
int cal(int u , int d){
    for(int i = 1; i <= m; i ++){
        int ma = 0 , mi = 1e9;
        for(int j = u; j <= d; j ++){
            ma = max(ma , a[j][i]);
            mi = min(mi , a[j][i]);
        }
        nowa[i] = ma;nowi[i] = mi;
    }
    build(1 , m , 1);
    int r = 1 , ans = 0;
    for(int l = 1; l <= m; l ++){
        while(r <= m && queryma(l , r ,1 , m , 1) - querymi(l , r, 1 , m , 1) <= k){
            r ++;
        }
        ans = max(ans , (d - u + 1) * (r - l));
    
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d",&k);
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j ++){
            ans = max(ans , cal(i , j));
        }
    }
    printf ("%d\n",ans);

return 0;
}

~~~

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

新breath

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

The 3n + 1 problem （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

最大子矩阵(线段树题解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【计算球体积】（C语言代码）

最好的，

1162答案错误，为什么

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

新breath

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C++代码）

The 3n + 1 problem （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

最大子矩阵(线段树题解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【计算球体积】 （C语言代码）

最好的，

1162答案错误，为什么

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

　　评论区

【计算球体积】（C语言代码）

C二级辅导-等差数列（C语言代码）